2452. Words Within Two Edits of Dictionary LeetCode Solution

In this guide, you will get 2452. Words Within Two Edits of Dictionary LeetCode Solution with the best time and space complexity. The solution to Words Within Two Edits of Dictionary problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Words Within Two Edits of Dictionary solution in C++
Words Within Two Edits of Dictionary solution in Java
Words Within Two Edits of Dictionary solution in Python
Additional Resources

2452. Words Within Two Edits of Dictionary LeetCode Solution image

Problem Statement of Words Within Two Edits of Dictionary

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.

Complexity Analysis

Time Complexity: O(q \cdot |\texttt{dictionary}||\texttt{dictionary[i]}|)
Space Complexity: O(q)

2452. Words Within Two Edits of Dictionary LeetCode Solution in C++

class Solution {
 public:
  vector<string> twoEditWords(vector<string>& queries,
                              vector<string>& dictionary) {
    vector<string> ans;

    for (const string& query : queries)
      for (const string& word : dictionary)
        if (inner_product(query.begin(), query.end(), word.begin(), 0, plus<>(),
                          not_equal_to<char>()) < 3) {
          ans.push_back(q);
          break;
        }

    return ans;
  }
};
/* code provided by PROGIEZ */

2452. Words Within Two Edits of Dictionary LeetCode Solution in Java

class Solution {
  public List<String> twoEditWords(String[] queries, String[] dictionary) {
    List<String> ans = new ArrayList<>();

    for (final String query : queries)
      for (final String word : dictionary)
        if (getDiff(query, word) < 3) {
          ans.add(query);
          break;
        }

    return ans;
  }

  private int getDiff(final String query, final String word) {
    int diff = 0;
    for (int i = 0; i < query.length(); ++i)
      if (query.charAt(i) != word.charAt(i))
        ++diff;
    return diff;
  }
}
// code provided by PROGIEZ

2452. Words Within Two Edits of Dictionary LeetCode Solution in Python

class Solution:
  def twoEditWords(
      self,
      queries: list[str],
      dictionary: list[str],
  ) -> list[str]:
    return [query for query in queries
            if any(sum(a != b for a, b in zip(query, word)) < 3
                   for word in dictionary)]
 # code by PROGIEZ