Example 1:
Given words = `["abc", "abd", "abcd", "adc"]` and target = `"ac"`, k = `1`
Return `["abc", "adc"]`
Input:
["abc", "abd", "abcd", "adc"]
"ac"
1
Output:
["abc","adc"]
Explanation:
"abc" remove "b"
"adc" remove "d"
Example 2:
Input:
["acc","abcd","ade","abbcd"]
"abc"
2
Output:
["acc","abcd","ade","abbcd"]
Explanation:
"acc" turns "c" into "b"
"abcd" remove "d"
"ade" turns "d" into "b" turns "e" into "c"
"abbcd" gets rid of "b" and "d"
思路:滚动数组。用字典树对dfs进行优化。
class TrieNode{
public TrieNode[] sons;
public boolean isWord;
public String word;
public TrieNode() {
int i;
sOns= new TrieNode[26];
for (i = 0; i <26; ++i) {
sons[i] = null;
}
isWord = false;
}
static public void Insert(TrieNode p, String word) {
int i;
char[] s = word.toCharArray();
for (i = 0; i res;
// p is the current TrieNode
// f[] representss f[Sp][...]
void dfs(TrieNode p, int[] f) {
int[] newf;
int i;
if (p.isWord && f[n] <= K) {
res.add(p.word);
}
for (int c = 0; c <26; ++c) {
if (p.sons[c] == null) {
continue;
}
// calc newf
newf = new int[n + 1];
// newf[...]: f[Sp + c][....]
// newf[j] = Math.min(Math.min(f[j], newf[j-1]), f[j-1]) + 1;
for (i = 0; i <= n; ++i) {
newf[i] = f[i] + 1;
}
for (i = 1; i <= n; ++i) {
newf[i] = Math.min(newf[i], f[i - 1] + 1);
}
for (i = 1; i <= n; ++i) {
if (target[i - 1] - ‘a‘ == c) {
newf[i] = Math.min(newf[i], f[i - 1]);
}
newf[i] = Math.min(newf[i - 1] + 1, newf[i]);
}
dfs(p.sons[c], newf);
}
}
public List kDistance(String[] words, String targets, int k) {
res = new ArrayList();
K = k;
TrieNode root = new TrieNode();
int i;
for (i = 0; i