Store each of the words in array in a trie and mark the end of the word by its corresponding entry in the second array. Now if u are searching for a word it'll take O(length of word) if there is a mismatch at any point you know the word is not present in array1 and add it to the trie or else the entire string might match but not terminate in an index implying the word being searched for is a prefix for a word already present. Add the entry if not present to the trie as well as to the array append the index of the word in trie with value entered by the user.
On Saturday, 16 June 2012 20:36:42 UTC+5:30, algogeek wrote: > > could u explain how would you use a trie for this?? > > On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote: >> >> Hi, >> >> *There are two arrays of length 100 each. Each of these has initially n >> (n<=100) >> elements. First array contains names and the second array contains numbers >> such that ith name in array1 corresponds to ith number in array2. >> Write a program which asks the user to enter a name, finds it in array1,* >> >> *a. if it exists, then print the corresponding number in array2, >> b. else ask the user to input its associated number and add the number and >> name to array2 and array1 respectively, and update the size of list* >> >> I can think of solving it through linear walk to the array. Anyone with >> more optimized algorithm like BST or HashTable? >> >> comments are welcome >> >> >> Thanks >> >> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/mJL9Nk2nSM4J. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
