Lintcode 623. K Edit Distance

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

Given words = ["abc", "abd", "abcd", "adc"] and target = "ac", k = 1
Return ["abc", "adc"]




Code (Java):

public class Solution {
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */
    public List<String> kDistance(String[] words, String target, int k) {
        List<String> ans = new ArrayList<>();
        if (words == null || words.length == 0 || k < 0) {
            return ans;
        }
        
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        TrieNode p = trie.root;
        
        int[] dp = new int[target.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }
        
        kDistanceHelper(p, dp, target, k, ans);
        
        return ans;
    }
    
    private void kDistanceHelper(TrieNode p, int[] dp, String target, int k, List<String> ans) {
        if (p == null) {
            return;
        }
        
        if (p.leaf && dp[target.length()] <= k) {
            ans.add(p.word);
        }
        
        int[] curr = new int[target.length() + 1];
        curr[0] = dp[0] + 1;
        
        for (char c = 'a'; c <= 'z'; c++) {
            if (p.children[c - 'a'] != null) {
                for (int j = 1; j <= target.length(); j++) {
                    if (c == target.charAt(j - 1)) {
                        curr[j] = dp[j - 1];
                    } else {
                        curr[j] = Math.min(dp[j - 1], Math.min(dp[j], curr[j - 1])) + 1;
                    }
                }
                kDistanceHelper(p.children[c - 'a'], curr, target, k, ans);
            }
        }
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            p = p.children[c - 'a'];
        }
        
        p.leaf = true;
        p.word = word;
    }
}

class TrieNode {
    TrieNode[] children;
    boolean leaf;
    String word;
    
    public TrieNode() {
        children = new TrieNode[26];
        leaf = false;
        word = "";
    }
}