Trie-Trie-Trie!!! - Part 3

This problem is another instance of Trie, with a simple recursive function to check for the partial matches. Straightforward. Code is below, cheers, ACC.

Words Within Two Edits of Dictionary - LeetCode

2452. Words Within Two Edits of Dictionary

Medium

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

 

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

 

Constraints:

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• All queries[i] and dictionary[j] are composed of lowercase English letters.

Accepted

11,817

Submissions

19,739

public IList TwoEditWords(string[] queries, string[] dictionary)
{
    Trie trie = new Trie();

    foreach (string word in dictionary)
        trie.Insert(word);

    List retVal = new List();
    foreach (string query in queries)
        if (trie.CheckWorkExistsKMismatches(query, 2))
            retVal.Add(query);

    return retVal;
}

public class Trie
{
    private Hashtable children = null;
    private int numberInstances = 0;
    public Trie()
    {
        children = new Hashtable();
        numberInstances = 0;
    }

    public void Insert(string word)
    {
        if (String.IsNullOrEmpty(word))
        {
            numberInstances++;
            return;
        }

        if (!children.ContainsKey(word[0])) children.Add(word[0], new Trie());
        Trie child = (Trie)children[word[0]];
        child.Insert(word.Substring(1));
    }

    public bool CheckWorkExistsKMismatches(string word, int k)
    {
        if (k < 0) return false;
        if (String.IsNullOrEmpty(word)) return true;

        foreach (char c in children.Keys)
        {
            Trie child = (Trie)children[c];
            if (child.CheckWorkExistsKMismatches(word.Substring(1), c == word[0] ? k : k - 1)) return true;
        }

        return false;
    }
}