Question

2452. 距离字典两次编辑以内的单词

English Version

题目描述

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回_ _queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

 

示例 1：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。

示例 2：

输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：
"yes" 需要超过 2 次编辑才能得到 "not" 。
所以我们返回空数组。

 

提示：

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• 所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

解法

方法一：暴力枚举

遍历 queries 中的每个单词，对于每个单词，遍历 dictionary 中的每个单词，判断两个单词不同字符的位置数是否小于 $3$，如果是，则将该单词加入结果集。

时间复杂度 $O(m\times n\times k)$。其中 $m$ 和 $n$ 分别是 queries 和 dictionary 的长度，而 $k$ 是 queries 和 dictionary 中单词的长度。

class Solution:
  def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
    ans = []
    for s in queries:
      for t in dictionary:
        if sum(a != b for a, b in zip(s, t)) < 3:
          ans.append(s)
          break
    return ans

class Solution {
  public List<String> twoEditWords(String[] queries, String[] dictionary) {
    List<String> ans = new ArrayList<>();
    int n = queries[0].length();
    for (var s : queries) {
      for (var t : dictionary) {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
          if (s.charAt(i) != t.charAt(i)) {
            ++cnt;
          }
        }
        if (cnt < 3) {
          ans.add(s);
          break;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
    vector<string> ans;
    for (auto& s : queries) {
      for (auto& t : dictionary) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i) cnt += s[i] != t[i];
        if (cnt < 3) {
          ans.emplace_back(s);
          break;
        }
      }
    }
    return ans;
  }
};

func twoEditWords(queries []string, dictionary []string) (ans []string) {
  for _, s := range queries {
    for _, t := range dictionary {
      cnt := 0
      for i := range s {
        if s[i] != t[i] {
          cnt++
        }
      }
      if cnt < 3 {
        ans = append(ans, s)
        break
      }
    }
  }
  return
}

function twoEditWords(queries: string[], dictionary: string[]): string[] {
  const n = queries[0].length;
  return queries.filter(querie => {
    for (const s of dictionary) {
      let diff = 0;
      for (let i = 0; i < n; i++) {
        if (querie[i] !== s[i] && ++diff > 2) {
          break;
        }
      }
      if (diff <= 2) {
        return true;
      }
    }
    return false;
  });
}

impl Solution {
  pub fn two_edit_words(queries: Vec<String>, dictionary: Vec<String>) -> Vec<String> {
    let n = queries[0].len();
    queries
      .into_iter()
      .filter(|querie| {
        for s in dictionary.iter() {
          let mut diff = 0;
          for i in 0..n {
            if querie.as_bytes()[i] != s.as_bytes()[i] {
              diff += 1;
            }
          }
          if diff <= 2 {
            return true;
          }
        }
        false
      })
      .collect()
  }
}