Skip to content

2452. Words Within Two Edits of Dictionary 👍

  • Time: $O(q \cdot |\texttt{dictionary}||\texttt{dictionary[i]}|)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
  }
}

1
2
3
4
5
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)]