Last Updated: 1 Oct, 2020
State Diagram
Moderate
Asked in companies
Given a state diagram in the form of a linked list, where each node represents a unique character and has two pointers('next' and 'random'), and a string 'str', find if this string is acceptable by the state diagram or not.
The state diagram looks something like this:
A string is said to be acceptable if and only if it matches the flow of states character by character and ends at final state i.e. state with next equal to 'null'. For the below diagram 'c' is the final state.
Note
1. The random pointer of a node may point to NULL or to itself.
2. All the nodes will represent unique characters.
3. All the characters will be the lowercase alphabets.
4. You can assume that the first state is the first character of the string.
Input Format:
The first line contains a single integer 'T' that represents the number of test cases.
The first line of each test case will contain an integer ‘N’ denoting the number of states(nodes) in the state diagram.
The second line contains a string of length ‘N’ where the ith state represents the ith character of the string.
The third line contains 'N' integers a1, a2,....,an, where ai denotes the position to which the ith node’s random pointer points to. If the ith pointer points to NULL, then ai = -1.
The fourth line contains the string 'STR', which needs to be checked for the given state diagram.
Output Format:
Print “yes” in a single line if the string is acceptable by the given state diagram, “no” otherwise.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 < =T <= 10
1 <= N <= 26
1 <= ai <= N, or ai = -1(if pointing to NULL)
1 <= len(str) <= 10^5
Time Limit: 1 sec
Approaches
- This is just an implementation problem that can be easily solved using recursion.
- In each iteration, we will make two calls, one to the state pointed by the next pointer, and the other to the state pointed by the random pointer of the current node,
- If the character at the current state matches with the corresponding character of the string then we move forward, else we return.
- If the iteration reaches the final state, and the current character of the string is its last character and it matches the character at this state, then the string is accepted by the state diagram, and we return true.
- We can observe a few things while looking at the “RECURSION” approach.
- As mentioned in the problem statement, all the states will have unique characters, which means that any character of the given string will pass only if it goes through a unique state, as there will be at most one state which will have that character.
- The above observation makes it easier to move forward, as now we can make only one valid call in each iteration, thus making the overall time complexity linear.
- Notice that if the next and the random pointer of the current node(state), points towards the same node, then we don't need to call both the pointers separately.
- Thus, we can simply iterate through the string, check if the next pointer points to the current character, then move to the next state, or if the random pointer points to the current character, then move accordingly, else return false.
- If we are at the last character of the string, and also the current state is the final state, then we are done, and we return true.