# 1554. Strings Differ by One Character

## Description

Given a list of strings dict where all the strings are of the same length.

Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.

Example 1:

Input: dict = ["abcd","acbd", "aacd"]
Output: true
Explanation: Strings "abcd" and "aacd" differ only by one character in the index 1.


Example 2:

Input: dict = ["ab","cd","yz"]
Output: false


Example 3:

Input: dict = ["abcd","cccc","abyd","abab"]
Output: true


Constraints:

• The number of characters in dict <= 105
• dict[i].length == dict[j].length
• dict[i] should be unique.
• dict[i] contains only lowercase English letters.

Follow up: Could you solve this problem in O(n * m) where n is the length of dict and m is the length of each string.

## Solutions

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

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