Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2

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

Example 3:

1
2

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

Constraints:

  • The number of characters in dict <= 10^5
  • 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.

Solution

Method 1 - Hashing with Wildcards

Intuition

If two strings differ by exactly one character at the same index, then if we replace that character with a wildcard (e.g., ‘*’), the resulting string will be the same for both. We can use a hash set to check for such collisions efficiently.

Approach

For each string, for each index, replace the character at that index with a wildcard and check if this new string has been seen before. If yes, return true. Otherwise, add it to the set. If no such pair is found, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    bool differByOne(vector<string>& dict) {
        unordered_set<string> seen;
        int m = dict[0].size();
        for (const string& word : dict) {
            for (int i = 0; i < m; ++i) {
                string t = word;
                t[i] = '*';
                if (seen.count(t)) return true;
                seen.insert(t);
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func differByOne(dict []string) bool {
    seen := make(map[string]struct{})
    m := len(dict[0])
    for _, word := range dict {
        for i := 0; i < m; i++ {
            t := word[:i] + "*" + word[i+1:]
            if _, ok := seen[t]; ok {
                return true
            }
            seen[t] = struct{}{}
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public boolean differByOne(String[] dict) {
        Set<String> seen = new HashSet<>();
        int m = dict[0].length();
        for (String word : dict) {
            for (int i = 0; i < m; i++) {
                String t = word.substring(0, i) + "*" + word.substring(i+1);
                if (seen.contains(t)) return true;
                seen.add(t);
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fun differByOne(dict: Array<String>): Boolean {
    val seen = mutableSetOf<String>()
    val m = dict[0].length
    for (word in dict) {
        for (i in 0 until m) {
            val t = word.substring(0, i) + "*" + word.substring(i+1)
            if (t in seen) return true
            seen.add(t)
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def differByOne(dict: list[str]) -> bool:
    seen = set()
    m = len(dict[0])
    for word in dict:
        for i in range(m):
            t = word[:i] + '*' + word[i+1:]
            if t in seen:
                return True
            seen.add(t)
    return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::HashSet;
pub fn differ_by_one(dict: Vec<String>) -> bool {
    let m = dict[0].len();
    let mut seen = HashSet::new();
    for word in &dict {
        let bytes = word.as_bytes();
        for i in 0..m {
            let mut t = bytes.to_vec();
            t[i] = b'*';
            if seen.contains(&t) {
                return true;
            }
            seen.insert(t);
        }
    }
    false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function differByOne(dict: string[]): boolean {
    const seen = new Set<string>();
    const m = dict[0].length;
    for (const word of dict) {
        for (let i = 0; i < m; i++) {
            const t = word.slice(0, i) + '*' + word.slice(i + 1);
            if (seen.has(t)) return true;
            seen.add(t);
        }
    }
    return false;
}

Complexity

  • ⏰ Time complexity: O(n * m) where n is the number of strings and m is the length of each string.
  • 🧺 Space complexity: O(n * m) for storing the wildcarded strings.