Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Suppose you are supplied with a file containing a list of words like ABC,ACD, ABC
( say each word in new line ). now you have to suggest algorithm for this problem -
When a user type some character, we have to suggest him next character and basis of
suggestion is that the character you are going to suggest should have maximum occurrence at that position with the given prefix.
For example , Let's say words are
ABC
ACD
ABC
Now if user types 'A' we have to suggest him 'B' as next character with the prefix ‘A’, ‘B’
has 2 times, and ‘C’ has 1. similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index since C has 2 times
keywords:
Constraint: the given prefix -> check its occurrence
ask: maximum occurrence char -> if there are more than one, check first occurrence with smaller index
A B ... Z
/ \
B C
/ \ \
C A D
[ABC count = 2, leaf = true] [ACD 1]
for example:
ABC
ABC
ABC (ABC prefix count = 3) C
ABA (ABA prefix count = 1)
Work on three string and put into trie, add count variable
ABC
ACD
ABC
A
/ \
B iterate 2 C iterate 1
/ \
C “ABC” 2 ACD “ACD 1”
https://docs.google.com/document/d/1Wyuaq9vTShZmjX9MpHJhcYDSNi40bKZSOcGbqH5vFho/edit?usp=sharing
Class Node{
public char c;
public int number;
public Node[] Children; // 26, 256
Public Node(char cc)
{
C = cc;
}
};
Private static Node addToTrie(string[] words)
{
if(words == null)
Return null;
// dummy node
Var dummyNode = new Node(‘’);
foreach(var word in words)
{
Var iterate = dummyNode;
// foreach(var item in word) // ABC
for(int index = 0; index < word.Length; index++)
{
Var item = word[index];
Var currentIndex = (int) item;
if(iterate .Children[currentIndex] == null)
{
iterate .Children[currentIndex] = new Node(item);
iterate .Children[currentIndex].number = 1;
}
Else
{
iterate .Children[currentIndex].number++;
}
if(index == word.Length - 1)
iterate.Children[currentIndex].WordInDict = false;
Iterate = iterate .Children[currentIndex];
}
}
Return dummyNode;
}
//ABC
//ACD
//ABC
// test case: given prefix “A”, find ‘B’
Private static char PrefixSuggest(string prefix, Node trie) // A
{
if(prefix == null || trie == null)
Return null;
Var iterate = trie; // dummy node
Var length = prefix.Length; // 1
Var index = 0;
while(iterate != null && index < length) // find the prefix first, and then look up its children and find its maximum number
{
Var visit = prefix[index];
Iterate = trie[(int)visit];
if(index == length - 1)
{
// find maximum value of children
Var maxIndex = 0;
Var maxNo = 0;
for(int i = 0; i < 256; i++)
{
if(iterate.children[i] != null && iterate.children[i].number > maxNo)
{
maxIndex = i;
maxNo = iterate.children[i].number;
}
}
index++;
Return (char) maxIndex;
}
}
Return ‘’; // default no found ->
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.