DescriptionNeal is very curious about combinatorial problems, and now here comes a problem about words. Knowing that Ray has a photographic memory and this may not trouble him, Neal gives it to Jiejie. Since Jiejie can’t remember numbers clearly, he just uses sticks to help himself. Allowing for Jiejie’s only 20071027 sticks, he can only record the remainders of the numbers divided by total amount of sticks. The problem is as follows: a word needs to be divided into small pieces in such a way that each piece is from some given set of words. Given a word and the set of words, Jiejie should calculate the number of ways the given word can be divided, using the words in the set.
Input
The input file contains multiple test cases. For each test case: the first line contains the given word whose length is no more than 300 000. The second line contains an integer S, 1 ≤ S ≤ 4000. Each of the following S lines contains one word from the set. Each word will be at most 100 characters long. There will be no two identical words and all letters in the words will be lowercase. There is a blank line between consecutive test cases. You should proceed to the end of file.
Output
For each test case, output the number, as described above, from the task description modulo 20071027.
Given a list of word and a target word, output all the words for each the edit distance with the target no greater than k. e.g. [abc, abd, abcd, adc], target "ac", k = 1, output = [abc, adc] Naive Solution: A naive solution would be, for each word in the list, calculate the edit distance with the target word. If it is equal or less than k, output to the result list. If we assume that the average length of the words is m, and the total number of words in the list is n, the total time complexity is O(n * m^2). A better solution with a trie: The problem with the previous solution is if the given list of the words is like ab, abc, abcd, each time we need to repeatedly calculate the edit distance with the target word. If we can combine the prefix of all words together, we can save lots of time.
public List<String> findKEditDistance(String[] strs, String target, int k) {
List<String> res = new ArrayList<>();
if(strs.length==0) return res;
Trie trie = new Trie();
TrieNode root = trie.buildTrie(strs);
int[] distance = new int[target.length()+1];
for(int i = 0;i<distance.length;i++) distance[i] = i;
helper(target,res,root,distance,k,"");
return res;
}
private void helper(String target, List<String> res, TrieNode root,
int[] distance, int k, String tmp) {
if(root.isWord) {
if(distance[target.length()]<=k) res.add(tmp);
return;
}
for(int i = 0;i<26;i++) {
if(root.children[i]==null) continue;
int[] curdistance = new int[target.length()+1];
//this +1 is to add the processing character, which is (char)(i+'a')
curdistance[0] = tmp.length()+1;
//use curdistance and distance to represent edit distance for tmp and target
//distance[j] means edit distance between tmp and target[0,j)
for(int j = 1;j<distance.length;j++) {
if(target.charAt(j-1)==(char)(i+'a')) curdistance[j] = distance[j-1];
// if character matches, no insert, delete or replace. so no increasing edit distance
//current edit distance for tmp and target[0,j) is distance[j-1]
else {
//not match, either delete, insert or replace character on tmp
curdistance[j] = Math.min(Math.min(distance[j-1], distance[j]), curdistance[j-1])+1; //+1?
//distance[j-1] means replace tmp.charAt(j-1) with target.charAt(j-1)
//distance[j] means delete tmp.charAt(j-1)
//curdistance[j-1] means add target.charAt(j-1) after tmp.charAt(j-1)
}
}
helper(target,res,root.children[i],curdistance,k,tmp+(char)(i+'a'));
}
}
}
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isWord = false;
}
class Trie {
public void insert(TrieNode root, String str) {
TrieNode cur = root;
for(int i = 0;i<str.length();i++) {
char c = str.charAt(i);
if(cur.children[c-'a']==null) cur.children[c-'a'] = new TrieNode();
cur = cur.children[c-'a'];
}
cur.isWord = true;
}
public TrieNode buildTrie(String[] strs) {
TrieNode root = new TrieNode();
for(String str:strs) insert(root,str);
return root;
}
}
X. Brute Force https://github.com/awangdev/LintCode/blob/master/Java/K%20Edit%20Distance.java
We can calculate min moves needed to reach target with dp
dp[i][j] represents # steps to convert S[0, i - 1] to T[0, j - 1]
dp[m][n] is the minimum moves
It's double sequence dp, initialize with [m+1][n+1]
dp[0][0] = 0. no sequence to compare/edit.
init: if i == 0, take j steps to become T. if j == 0, takes i steps to become S.
Apply the dp for all words
Some pre-validations:
- length diff > k, skip
- equal to target: just return
public List<String> kDistance(String[] words, String target, intk) {
List<String> rst = new ArrayList<>();
if (words == null || words.length == 0 || target == null || k <= 0) {
returnrst;
}
for (String word: words) {
if (validate(word, target, k)) {
rst.add(word);
}
}
returnrst;
}
privateboolean validate(String word, String target, intk) {
if (word.equals(target)) {
returntrue;
}
if (Math.abs(word.length() - target.length()) > k) {
