Two Words One Letter Apart

Medium

You are given a list of distinct words words, all of the same length. Check whether two of them differ in exactly one position, with the same letter in every other place. Return True if such a pair exists and False otherwise. Trying every pair is the obvious way; aim for O(n · m), where n is the number of words and m is their length.

Example 1

words=['lamp', 'ramp', 'rump', 'dump'] → True

"lamp" and "ramp" differ only in the first letter, so such a pair exists.

Example 2

words=['abc', 'bca', 'cab'] → False

Any two of the words differ in all three positions, so there is no pair.

Example 3

words=['x'] → False

There is only one word, nothing to compare it with.

Constraints

1 ≤ len(words)
All words have the same length, at least 1
The total length of all words is at most 10⁵
All words are distinct
Words consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Hash Function Rolling Hash

Similar problems

Recurring Gene Windows Medium Every Bit Pattern Inside Medium Evenly Mixed Digit Pieces Medium Longest Piece Seen Twice Medium Counting Distinct Substrings Medium

Input

words=['lamp', 'ramp', 'rump', 'dump']

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.