前往
大廳
主題

LeetCode - 859. Buddy Strings 解題心得

Not In My Back Yard | 2021-01-27 00:00:08 | 巴幣 0 | 人氣 333

題目連結:


題目意譯:
給定兩個字串 A 和 B,其只由小寫字母組成。回傳真(True),如果你可以交換(一定要作一次且僅此一次交換)兩個於 A 之中的字母得到的結果會等於 B;反之,回傳假(False)。

交換兩個字母定義為取兩個索引值 i 和 j (從 0 開始計算)且 i ≠ j ,然後交換兩字母 A[i] 以及 A[j]。例如,交換索引值 0 以及 2 的字母對於 "abcd" 將得到 "cbad"。

限制:
0 ≦ A.length ≦ 20000
0 ≦ B.length ≦ 20000
A 和 B 只由小寫字母組成。



範例測資:
範例 1:
輸入: A = "ab", B = "ba"
輸出: true
解釋: 你可以交換 A[0] = 'a' 以及 A[1] = 'b' 而得到 "ba",其與字串 B 相同。

範例 2:
輸入: A = "ab", B = "ab"
輸出: false
解釋: 唯二能交換的字母為 A[0] = 'a' 和 A[1] = 'b',其將得到 "ba" 且不等於 B。

範例 3:
輸入: A = "aa", B = "aa"
輸出: true
解釋: 你可以交換 A[0] = 'a' 以及 A[1] = 'a' 而得到 "aa",其與字串 B 相同。

範例 4:
輸入: A = "aaaaaaabc", B = "aaaaaaacb"
輸出: true

範例 5:
輸入: A = "", B = "aa"
輸出: false


解題思維:
首先判斷 A 的長度以及 B 的長度。如果 |A| 不等於 |B|,那當然就不可能藉由交換來使得 A = B,所以回傳假。

再來同時比較 A 與 B 的每個字元。如果 A 的第 i 個字元 A[i] 不等於 B 的第 i 個字元 B[i],則先判斷這是不是第一次發生(有無先前的不同處)。如果是則紀錄這次的不同;反之則交換上一次發生時的字元 A[last] 與現在的字元 A[i],看是否 A = B。如果是則回傳真,反之為假。

如果上面掃完沒有得出結論,則我們再判斷先前有沒有不同處(也就是 A 與 B 有一處不同)。如果是則回傳;若非(代表 A 原本就等於 B)則再掃一次 A 並統計每種字元的出現次數,只要有一種字元出現兩次以上(含)就可以交換兩者而保持 A = B,所以回傳真。若沒有任何字元出現至少兩次則回傳假。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作