本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個字符串?dāng)?shù)組 words ，每一個字符串長度都相同，令所有字符串的長度都為 n 。

每個字符串 words[i] 可以被轉(zhuǎn)化為一個長度為 n - 1 的 差值整數(shù)數(shù)組 difference[i] ，其中對于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] - words[i][j] 。注意兩個字母的差值定義為它們在字母表中 位置 之差，也就是說 'a' 的位置是 0 ，'b' 的位置是 1 ，'z' 的位置是 25 。

• 比方說，字符串 "acb" 的差值整數(shù)數(shù)組是 [2 - 0, 1 - 2] = [2, -1] 。

words 中所有字符串 除了一個字符串以外 ，其他字符串的差值整數(shù)數(shù)組都相同。你需要找到那個不同的字符串。

請你返回 words中 差值整數(shù)數(shù)組 不同的字符串。

示例 1：

輸入：words = ["adc","wzy","abc"]
輸出："abc"
解釋：
- "adc" 的差值整數(shù)數(shù)組是 [3 - 0, 2 - 3] = [3, -1] 。
- "wzy" 的差值整數(shù)數(shù)組是 [25 - 22, 24 - 25]= [3, -1] 。
- "abc" 的差值整數(shù)數(shù)組是 [1 - 0, 2 - 1] = [1, 1] 。
不同的數(shù)組是 [1, 1]，所以返回對應(yīng)的字符串，"abc"。

示例 2：

輸入：words = ["aaa","bob","ccc","ddd"]
輸出："bob"
解釋：除了 "bob" 的差值整數(shù)數(shù)組是 [13, -13] 以外，其他字符串的差值整數(shù)數(shù)組都是 [0, 0] 。

提示：

• 3 <= words.length <= 100
• n == words[i].length
• 2 <= n <= 20
• words[i] 只含有小寫英文字母。

---

解法 遍歷

不使用哈希表，也不直接求出每個字符串的差分?jǐn)?shù)組、再進行計數(shù)比較。思路很簡單：設(shè)當(dāng)前位置為 $i$ ，則某個字符串 $words[j]$ 當(dāng)前位置的差分值由$words[j][i]?words[j][i?1]$ 得到。我們遍歷所有位置，并對每個位置下的、所有字符串的差分值進行比較。

設(shè) $words[0][i]?words[0][i?1]$ 的差分值為 $d$ ，如果其他字符數(shù)組 $words[j]$ 的差分值和 $d$ 不等，則累計不等的數(shù)量、記錄對應(yīng)下標(biāo) $idx$ 。

• 如果不等的數(shù)量為 $0$ ，說明這個位置 $i$ 的所有差分值都相同；
• 如果不等的數(shù)量不為 $0$ ：
  • 不等的數(shù)量為 $m?1$ ，$m$ 為字符數(shù)組個數(shù)，根據(jù)題意，只有一個字符串的差值數(shù)組不同，則與眾不同的就是 $words[0]$ ；
  • 否則唯一不同的是 $words[idx]$

class Solution {public String oddString(String[] words) {int n = words[0].length();for (int i = 1; i < n; ++i) {int d = words[0].charAt(i) - words[0].charAt(i - 1);int idx = 0, cnt = 0;for (int j = 1; j < words.length; ++j) {int td = words[j].charAt(i) - words[j].charAt(i - 1);if (td != d) {idx = j;++cnt;} }if (cnt == 0) continue;if (cnt == words.length - 1) return words[0];return words[idx];}return "";}
}

復(fù)雜度分析：

• 時間復(fù)雜度：$O(nm)$ ，$n$ 為每個字符串的長度，$m$ 為字符串?dāng)?shù)組的長度
• 空間復(fù)雜度：$O(1)$