2451. Odd String Difference
Description
You are given an array of equal-length strings words
. Assume that the length of each string is n
.
Each string words[i]
can be converted into a difference integer array difference[i]
of length n - 1
where difference[i][j] = words[i][j+1] - words[i][j]
where 0 <= j <= n - 2
. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a'
is 0
, 'b'
is 1
, and 'z'
is 25
.
- For example, for the string
"acb"
, the difference integer array is[2 - 0, 1 - 2] = [2, -1]
.
All the strings in words have the same difference integer array, except one. You should find that string.
Return the string in words
that has different difference integer array.
Example 1:
Input: words = ["adc","wzy","abc"] Output: "abc" Explanation: - The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1]. - The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1]. - The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. The odd array out is [1, 1], so we return the corresponding string, "abc".
Example 2:
Input: words = ["aaa","bob","ccc","ddd"] Output: "bob" Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].
Constraints:
3 <= words.length <= 100
n == words[i].length
2 <= n <= 20
words[i]
consists of lowercase English letters.
Solutions
Solution 1: Hash Table Simulation
We use a hash table $d$ to maintain the mapping relationship between the difference array of the string and the string itself, where the difference array is an array composed of the differences of adjacent characters in the string. Since the problem guarantees that except for one string, the difference arrays of other strings are the same, we only need to find the string with a different difference array.
The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the length of the string and the number of strings, respectively.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|