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.
Solution: Comparing with first string.
Let us pick words[0] as a reference for comparison, assuming it’s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m – 1 different words which means words[0] itself is bad.
Time complexity: O(m*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: string oddString(vector<string>& words) { const int m = words.size(); const int n = words[0].size(); int count = 0; int bad = 0; for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) { if (words[i][j] - words[i][j - 1] != words[0][j] - words[0][j - 1]) { ++count; bad = i; break; } } return words[count == 1 ? bad : 0]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment