Last Updated: 19 Nov, 2021
Similar Name
Hard
Asked in companies
Being a class monitor, you have a list of names of your class students. Your task is to find the first name from the list, which is similar to any other name occurring before it in the list.
Two names, name1 and name2, are similar if at least one of the following conditions holds.
Both names are identical.
name1 is a prefix of name2.
name2 is a prefix of name1.
Print the first name from the list, which is similar to any other name present in the prefix part of the list. If no such name is found, print “not found”.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The first line contains one integer 'N', denoting the number of names in the list.
Next 'N' lines contain one string each, denoting the names in the list.
Output Format:
For each test, print one string, denoting the first name in the list, similar to another name in the prefix part of the list. If no such name is found, print “not found”.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= the length of name[i] <= 60 i ∈ (1,N)
All letters in name[i] are lowercase english letters, in the range 'a' to 'j' inclusive.
Note - Sum of 'N' over all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: Run two loops (nested) to find all possible pairs of names and check similarity between them. If a pair at index (i, j) is similar where (i < j), then the name at index ‘j’ is the answer for such a pair. Finally, return the name with minimum ‘j’ among all generated pairs.
Algorithm:
- Iterate a for loop, j = 1 to N.
- Iterate another for loop, i = 1 to j-1.
- If any of the following conditions hold.
- [i-th name] is a prefix of [j-th name].
- [j-th name] is a prefix of [i-th name].
- Both names are identical.
- Return [j-th name] from the list.
- If any of the following conditions hold.
- Iterate another for loop, i = 1 to j-1.
- Return “not found”.
Approach: To find similarity between names/strings, an efficient data structure is trie.
The nodes in our trie will contain the following two informations:-
- A flag which indicates if a name ends at this node.
- An array of pointers that contains the pointers to next nodes, reachable from each letter in names. Initially, all pointers point to a NULL value.
We insert the names in the trie, in the same order we are getting in input data. When i-th name is inserted, trie will already have all names to which i-th name will be compared to become an answer, i.e., all names in the prefix part of the list are already inserted in the trie. While inserting i-th name in trie, if a similarity is found, i-th name becomes our answer, and there is no need to proceed with the remaining names.
How to check similarity while inserting a name in trie?
- While inserting a name in trie, if a node is found for which flag indicates the ending of some node, then that particular name is a prefix of the current name.
- If the current name is completely inserted, but the next pointer from the last node is not NULL, it means that some other name has been inserted through this path and our current name is a prefix of that name.
If all names are successfully inserted in trie, return "not found".
Algorithm:
- Structure of a node :
- A flag that indicates if a name ends at this node. Initialize with 'false'.
- An array of pointers. Initialize all values with NULL.
- Initialize trie with an empty root node.
- Iterate a loop for names in the list.
- Initialize starting node (for traversal in trie) with the root node.
- Let our current name be 'curr_name'.
- Iterate a loop for characters in 'curr_name'.
- Let our current letter be 'ch'.
- If this is the last character of 'curr_name' and the child node using 'ch' is not NULL, return 'curr_name' as the answer.
- Mark' ch' as inserted and move to the corresponding child node.
- If the flag is 'true' for this node, return 'curr_name' as the answer.
- Mark flag of current node as 'true'.
- If no similarity is found, return "not found".