Question

1554. 只有一个不同字符的字符串

English Version

题目描述

给定一个字符串列表 dict ，其中所有字符串的长度都相同。

当存在两个字符串在相同索引处只有一个字符不同时，返回 True ，否则返回 False 。

 

示例 1：

输入：dict = ["abcd","acbd", "aacd"]
输出：true
解释：字符串 "abcd" 和 "aacd" 只在索引 1 处有一个不同的字符。

示例 2：

输入：dict = ["ab","cd","yz"]
输出：false

示例 3：

输入：dict = ["abcd","cccc","abyd","abab"]
输出：true

 

提示：

• dict 中的字符数小于或等于 10^5 。
• dict[i].length == dict[j].length
• dict[i] 是互不相同的。
• dict[i] 只包含小写英文字母。

 

进阶：你可以以 O(n*m) 的复杂度解决问题吗？其中 n 是列表 dict 的长度，m 是字符串的长度。

解法

方法一

class Solution:
  def differByOne(self, dict: List[str]) -> bool:
    s = set()
    for word in dict:
      for i in range(len(word)):
        t = word[:i] + "*" + word[i + 1 :]
        if t in s:
          return True
        s.add(t)
    return False

class Solution {
  public boolean differByOne(String[] dict) {
    Set<String> s = new HashSet<>();
    for (String word : dict) {
      for (int i = 0; i < word.length(); ++i) {
        String t = word.substring(0, i) + "*" + word.substring(i + 1);
        if (s.contains(t)) {
          return true;
        }
        s.add(t);
      }
    }
    return false;
  }
}

class Solution {
public:
  bool differByOne(vector<string>& dict) {
    unordered_set<string> s;
    for (auto word : dict) {
      for (int i = 0; i < word.size(); ++i) {
        auto t = word;
        t[i] = '*';
        if (s.count(t)) return true;
        s.insert(t);
      }
    }
    return false;
  }
};

func differByOne(dict []string) bool {
  s := make(map[string]bool)
  for _, word := range dict {
    for i := range word {
      t := word[:i] + "*" + word[i+1:]
      if s[t] {
        return true
      }
      s[t] = true
    }
  }
  return false
}