Hackercup 2015: Autocomplete - Coding in A Smart Way
Since you crave state-of-the-art technology, you've just purchased a phone with a great new feature: autocomplete! Your phone's version of autocomplete has some pros and cons. On the one hand, it's very cautious. It only autocompletes a word when it knows exactly what you're trying to write. On the other hand, you have to teach it every word you want to use.
You have N distinct words that you'd like to send in a text message in order. Before sending each word, you add it to your phone's dictionary. Then, you write the smallest non-empty prefix of the word necessary for your phone to autocomplete the word. This prefix must either be the whole word, or a prefix which is not a prefix of any other word yet in the dictionary.
What's the minimum number of letters you must type to send all N words?
Example: Assume you have 5 words in the order: hi, hello, lol, hills, hill. Then you need to type "h" (for "hi"), "he" for ("hello"), "l" (for "lol"), "hil" (for "hills", because "h" and "hi" are also prefix of "hi"), "hill" (for "hill"). In total, you must type 11 characters.
Constraints: The words are made up of only lower-case alphabetic characters. The words are pairwise distinct.
Trie:
Assume L is the length of longest word and W is the number of words, the program runs in O(L.W) time and uses a memory of O(L.W) nodes.
https://github.com/ChenXinyue/AlgorithmPractices/blob/master/CodeForces/2015%20Facebook%20Hacker%20Cup%2C%20Round%201-B-Autocomplete.java
Read full article from Hackercup 2015: Autocomplete - Coding in A Smart Way
Since you crave state-of-the-art technology, you've just purchased a phone with a great new feature: autocomplete! Your phone's version of autocomplete has some pros and cons. On the one hand, it's very cautious. It only autocompletes a word when it knows exactly what you're trying to write. On the other hand, you have to teach it every word you want to use.
You have N distinct words that you'd like to send in a text message in order. Before sending each word, you add it to your phone's dictionary. Then, you write the smallest non-empty prefix of the word necessary for your phone to autocomplete the word. This prefix must either be the whole word, or a prefix which is not a prefix of any other word yet in the dictionary.
What's the minimum number of letters you must type to send all N words?
Example: Assume you have 5 words in the order: hi, hello, lol, hills, hill. Then you need to type "h" (for "hi"), "he" for ("hello"), "l" (for "lol"), "hil" (for "hills", because "h" and "hi" are also prefix of "hi"), "hill" (for "hill"). In total, you must type 11 characters.
Constraints: The words are made up of only lower-case alphabetic characters. The words are pairwise distinct.
Trie:
Assume L is the length of longest word and W is the number of words, the program runs in O(L.W) time and uses a memory of O(L.W) nodes.
private static char A = 'a';private static int SIZE = 26;public static void main(String[] args) throws FileNotFoundException{ Scanner in = new Scanner(new File("input2.txt")); int T = in.nextInt(); for(int i = 1; i <= T; i++){ int N = in.nextInt(); Node root = new Node(); int count = 0; for(int j = 0; j < N; j++){ String s = in.next(); count += shortestPrefix(s, root); } System.out.println("Case #" + i + ": " + count); } in.close();}private static int shortestPrefix(String s, Node root){ int length = s.length(); int result = length; Node currentNode = root; for(int i = 0; i < length; i++){ char c = s.charAt(i); int index = c - A; if(currentNode.child[index] == null){ currentNode.child[index] = new Node(); if(result == length){ result = i + 1; } } currentNode = currentNode.child[index]; } return result;} public static class Node{ public Node[] child = new Node[SIZE];}Read full article from Hackercup 2015: Autocomplete - Coding in A Smart Way
