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

题目描述

给定一个字符串列表 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⁵ 。
dict[i].length == dict[j].length
dict[i] 是互不相同的。
dict[i] 只包含小写英文字母。

解法

方法一

思考

判断是否存在恰好相差一位的两个词。词数与长度之积不超过 \(10^5\)，两两比较每位是平方级。

把每个词的每一位依次换成通配符，得到「忽略该位」的模式。若某模式已在集合中出现，则存在另一词与当前词只在该位不同。哈希集合保证均摊常数查询。

Python3JavaC++Go

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
}

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

题目描述

解法

方法一

评论