PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
TRIES
PROBLEM:
Given n passwords and q queries, find for each query the minimum number of keystrokes needed to key in a valid password.
EXPLANATION:
The first subtask can be solved in the naive way. For each string, we check all the possible passwords and find the minimum number of keystrokes needed to key in it from the the current string. Note that if the current string is s and the password is t, then the minimum number of keystrokes needed is |s| + |t| - 2lcp(s, t), where lcp(s, t) is the longest common prefix of s and t.
We need to optimize the current solution to solve Subtask 2. The easiest way is to store the passwords in a trie, and for each query, we go down the trie. For each node of the trie, store the length of the word of the minimum length in the subtree. Now, we can find the answer in O(Q + N) time where Q is the sum of length of all query strings and N is sum of length of all passwords. See the code for more details.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.