KEditDistance

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