Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1554. Strings Differ by One Character - Leetcode Solution

Code Implementation

class Solution:
    def differByOne(self, dict):
        seen = set()
        for word in dict:
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]
                if pattern in seen:
                    return True
                seen.add(pattern)
        return False
      
class Solution {
public:
    bool differByOne(vector<string>& dict) {
        unordered_set<string> seen;
        for (const string& word : dict) {
            for (int i = 0; i < word.size(); ++i) {
                string pattern = word.substr(0, i) + "*" + word.substr(i + 1);
                if (seen.count(pattern)) return true;
                seen.insert(pattern);
            }
        }
        return false;
    }
};
      
class Solution {
    public boolean differByOne(String[] dict) {
        Set<String> seen = new HashSet<>();
        for (String word : dict) {
            for (int i = 0; i < word.length(); ++i) {
                String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
                if (seen.contains(pattern)) return true;
                seen.add(pattern);
            }
        }
        return false;
    }
}
      
var differByOne = function(dict) {
    const seen = new Set();
    for (const word of dict) {
        for (let i = 0; i < word.length; ++i) {
            let pattern = word.slice(0, i) + "*" + word.slice(i + 1);
            if (seen.has(pattern)) return true;
            seen.add(pattern);
        }
    }
    return false;
};

Problem Description

Given a list of strings dict, determine if there exist two strings in the list that differ by exactly one character at the same position. In other words, you need to check if it is possible to pick two different strings from dict such that, for some index, all characters are the same except for that index. Each string in dict is of the same length, and you must not compare a string with itself.

Thought Process

The straightforward way to solve this problem is to compare every possible pair of strings and check if they differ by exactly one character. This approach is simple but inefficient for large inputs because it involves a lot of repeated work. To optimize, we look for a way to efficiently check if such a pair exists without comparing all pairs directly. The key insight is that if two strings differ by only one character, then replacing that differing character with a wildcard (like *) in both strings will result in the same pattern. For example, "abcd" and "abed" both become "ab*d" when the third character is replaced.

Solution Approach

To solve the problem efficiently, we use the following steps:
  • Iterate through each word in dict.
  • For each position in the word, create a new pattern by replacing the character at that position with a wildcard (e.g., *).
  • Store each generated pattern in a hash set.
  • If we generate a pattern that already exists in the set, it means there is another word in the list that differs by exactly one character at this position, so we return True.
  • If no such pattern is found after processing all words, return False.
We use a hash set for constant-time lookups, which makes the solution efficient.

Example Walkthrough

Consider the input dict = ["abcd", "abed", "aecd"]:
  • Take "abcd":
    • Replace index 0: "*bcd"
    • Replace index 1: "a*cd"
    • Replace index 2: "ab*d"
    • Replace index 3: "abc*"
    Add all these patterns to the set.
  • Next, "abed":
    • Replace index 0: "*bed"
    • Replace index 1: "a*ed"
    • Replace index 2: "ab*d" (already in set!)
    Since "ab*d" is already in the set, we know "abcd" and "abed" differ by only one character at index 2. We return True.
The process stops as soon as a match is found.

Time and Space Complexity

  • Brute-force approach: For each pair of strings, compare character by character. This is O(N^2 * L), where N is the number of strings and L is the length of each string.
  • Optimized approach (using patterns): For each of N strings, we generate L patterns, each taking O(L) time to create and insert/check in the set. So, total time is O(N * L^2).
  • Space complexity: We store up to N * L patterns in the set, so space is O(N * L).
The optimized approach is much faster for large inputs.

Summary

The key insight for solving the "Strings Differ by One Character" problem is to use pattern masking and hashing. By replacing each character with a wildcard and tracking these patterns, we can efficiently detect if any two strings differ by exactly one character. This approach avoids unnecessary comparisons and leverages hash set lookups for speed, making the solution both elegant and efficient.