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 是字符串的长度。

解法

哈希表。

将字符串列表中每个字符串进行处理，比如 "abcd" 处理成 "*bcd"、"a*cd"、"ab*d"、"abc*" 模式串，依次存入哈希表中。存入之前先判断哈希表中是否已存在该模式串，若是，说明存在两个字符串在相同索引处只有一个字符不同，直接返回 true。否则遍历结束返回 false。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

...