Question

Formatted question description: https://leetcode.ca/all/1554.html

 1554. Strings Differ by One Character

 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
 Output: 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:
     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.

Algorithm

Consider this example: {123,124,134,213}. How to quickly determine whether two numbers differ by only one digit?

The simpler method is: erase all the single digits, check the remaining values ​​{120,120,130,210}, and add them to the set once to determine whether there are duplicate elements. If we don’t find it, we can erase the tens digit and get {103,104,104,203}. Similarly, we can determine whether there are duplicate elements… For any digit, once we find that the remaining value after erasing is duplicated, then It means that at least one pair of numbers differs only by this digit.

This question is to extend the above ideas to strings. Use the rolling hash method to completely encode each string. Then examine each digit one by one, erase the complete code of each string, and check whether the remaining codes are repeated.

Code

Java

public class Strings_Differ_by_One_Character {

    class Solution {
        public boolean differByOne(String[] dict) {

            if (dict == null || dict.length < 2) {
                return false;
            }

            Set<String> set;
            for (int i = 0; i < dict[0].length(); i++) {
                set = new HashSet<>();
                for (String word : dict) {
                    if (!set.add(word.substring(0, i) + word.substring(i + 1))) {
                        return true;
                    }
                }
            }

            return false;
        }
    }

}

All Problems

All Solutions