Strings Differ by One Character

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atAirbnb

Strings Differ by One Character is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (rolling hash with one character removed), runs in O(n · m) expected time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from compare every pair up.

Problem

You are given a list dict of distinct words. All of them have the same length and use only lowercase letters.

Return true if some two words in the list differ in exactly one position (they have the same letter at every other index), and false otherwise.

Examples

Example 1

Input
dict = ["pqrs", "ptrz", "pqzs"]
Output
true
Why
"pqrs" and "pqzs" match everywhere except index 2.

Example 2

Input
dict = ["ab", "ba", "cc"]
Output
false
Why
Every pair of words differs in both positions.

Example 3

Input
dict = ["mnop", "xnop", "mnoq", "mnyp"]
Output
true
Why
"mnop" is one character away from each of the other three words.

Constraints

  • 1 <= dict.length; the total number of characters over all words is at most 10^5.
  • All words have the same length m >= 1.
  • Every word is made of lowercase English letters, and all words are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Compare every pairO(n² · m)O(1)
Masked words in a hash setO(n · m²)O(n · m)
Optimal (rolling hash with one character removed)O(n · m) expectedO(n)

1Compare every pair

TimeO(n² · m)n(n - 1) / 2 pairs, each compared in up to m steps.
SpaceO(1)Only loop counters.

For every pair of words, count the positions where they differ and stop early once the count reaches 2.

  1. For each pair (i, j) with i < j: count mismatching positions, stopping at 2.
  2. If the count is exactly 1, return true.
  3. Return false.
class Solution {
    public boolean differByOne(String[] dict) {
        int n = dict.length, m = dict[0].length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = 0;
                for (int k = 0; k < m && diff < 2; k++) {
                    if (dict[i].charAt(k) != dict[j].charAt(k)) diff++;
                }
                if (diff == 1) return true;
            }
        }
        return false;
    }
}

2Masked words in a hash set

TimeO(n · m²)m indices × n words × O(m) to build and hash each masked word.
SpaceO(n · m)One set of n masked words of length m at a time.

Two distinct words differ in exactly one place j exactly when they become equal after replacing index j with a wildcard. For each index j, put every masked word into a fresh hash set; a repeat means a matching pair.

  1. For each index j from 0 to m - 1, create an empty set.
  2. For each word, build word[0..j) + '*' + word(j..m).
  3. If the masked word is already in the set, return true; otherwise add it.
  4. Return false.
class Solution {
    public boolean differByOne(String[] dict) {
        int m = dict[0].length();
        for (int j = 0; j < m; j++) {
            Set<String> seen = new HashSet<>();
            for (String w : dict) {
                String masked = w.substring(0, j) + "*" + w.substring(j + 1);
                if (!seen.add(masked)) return true;
            }
        }
        return false;
    }
}

3Optimal (rolling hash with one character removed)

TimeO(n · m) expectedHashes take O(n · m) to build, and each of the m rounds handles n words in O(1) each; full comparisons only happen on hash matches, which are real matches except for rare collisions.
SpaceO(n)The n hashes plus one map of n entries per round.

Give every word a polynomial hash h = sum of value(c_k) · B^(m-1-k) mod P. Removing the character at index j changes the hash to h - value(c_j) · B^(m-1-j), which costs O(1). For each index j, group words by this masked hash; when two words collide, compare them directly (skipping index j) to rule out a false hash match.

  1. Compute pow[k] = B^k mod P and the full hash h[i] of each word (B = 27, letters map to 1..26, P = 1,000,000,007).
  2. For each index j: create a map from masked hash to the indices of words having it.
  3. For word i, masked = (h[i] - value(word[j]) · pow[m-1-j]) mod P, made non-negative.
  4. For each earlier word with the same masked hash, check that the two words agree everywhere except j; if so return true. Then add i to the bucket.
  5. Return false.
class Solution {
    public boolean differByOne(String[] dict) {
        final long MOD = 1_000_000_007L, BASE = 27;
        int n = dict.length, m = dict[0].length();
        long[] pow = new long[m];
        pow[0] = 1;
        for (int k = 1; k < m; k++) pow[k] = pow[k - 1] * BASE % MOD;
        long[] h = new long[n];
        for (int i = 0; i < n; i++) {
            long v = 0;
            for (int k = 0; k < m; k++) v = (v * BASE + (dict[i].charAt(k) - 'a' + 1)) % MOD;
            h[i] = v;
        }
        for (int j = 0; j < m; j++) {
            Map<Long, List<Integer>> buckets = new HashMap<>();
            for (int i = 0; i < n; i++) {
                long masked = (h[i] - (dict[i].charAt(j) - 'a' + 1) * pow[m - 1 - j] % MOD + MOD) % MOD;
                List<Integer> same = buckets.computeIfAbsent(masked, x -> new ArrayList<>());
                for (int other : same) {
                    if (sameExcept(dict[i], dict[other], j)) return true;
                }
                same.add(i);
            }
        }
        return false;
    }

    private boolean sameExcept(String a, String b, int skip) {
        for (int k = 0; k < a.length(); k++) {
            if (k != skip && a.charAt(k) != b.charAt(k)) return false;
        }
        return true;
    }
}

Edge cases to test

  • A single word, which has no partner
  • Words of length 1: any two distinct words differ in exactly one character
  • The differing position is the first or the last character
  • Pairs that differ in two or more positions must not count

Hints

Hint 1

Checking every pair works but is quadratic in the number of words. What do two matching words have in common?

Hint 2

If two words differ only at index j, they are identical once index j is blanked out. Try a hash set of masked words for each j.

Hint 3

Building each masked word costs O(m). A polynomial hash lets you remove one character from a word's hash in O(1).

FAQ

What is the best time complexity for Strings Differ by One Character?

Optimal (rolling hash with one character removed) runs in O(n · m) expected time and O(n) extra space. Hashes take O(n · m) to build, and each of the m rounds handles n words in O(1) each; full comparisons only happen on hash matches, which are real matches except for rare collisions.

Which pattern does Strings Differ by One Character use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Strings Differ by One Character?

Yes. Compare every pair takes O(n² · m) time and O(1) space. For every pair of words, count the positions where they differ and stop early once the count reaches 2.

Which edge cases should I test for Strings Differ by One Character?

A single word, which has no partner; Words of length 1: any two distinct words differ in exactly one character; The differing position is the first or the last character; Pairs that differ in two or more positions must not count.