前往
大廳
主題

LeetCode - 1790. Check if One String Swap Can Make Strings Equal 解題心得

Not In My Back Yard | 2022-10-18 12:00:14 | 巴幣 0 | 人氣 162

題目連結:


題目意譯:
你被給定兩字串 s1 和 s2,兩者長度相等。一次的字串交換為一種操作,其中你可以選擇一個字串中兩個索引值(不一定相異)並將位於這兩個索引值的字元交換。

如果在只對恰好其中一個字串做最多一次的字串交換的情況下可以使兩字串相同,則回傳真(True);反之,回傳假(False)。

限制:
1 ≦ s1.length, s2.length ≦ 100
s1.length == s2.length
s1 和 s2 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: s1 = "bank", s2 = "kanb"
輸出: true
解釋: 例如,將 s2 第一個和最後一個字元交換便可以得到 "bank"。

範例 2:
輸入: s1 = "attack", s2 = "defend"
輸出: false
解釋: 不可能只經由一次字串交換就使它們變為相同。

範例 3:
輸入: s1 = "kelb", s2 = "kelb"
輸出: true
解釋: 兩個字串已經一樣了,因此不需任何的字串交換。


解題思維:
同時掃過兩個字串並比較同位置的字元。可以看到如果:
不同處是 0 個,則不需做任何的字串交換,因此回傳真;
不同處是 1 個,則表示不論做幾次字串交換都會有一處不同,因此回傳假;
不同處大於 2 個,則代表一次字串交換不夠用(一次最多消掉兩個),因此回傳假;
最後不同處是恰好 2 個,則就是隨便挑一個字串(例如 s1)交換這兩處的字元然後再與另一個字串(承前例,s2)比較,如果一樣就回傳真;不一樣就回傳假。




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

創作回應

更多創作