KEditDistance

Given a set of strings which just has lower case letters and a target string, output all the strings for each the edit distance with the target no greater than k.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example

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