題目連結:
題目意譯:
你被給定兩個長度皆為 n 的字串 s1 和 s2,兩者皆由小寫英文字母組成。
你可以在任意次地任選一個字串上執行以下操作:
選擇任兩個索引值 i 和 j 滿足 i < j 且 j - i 為偶數,並將字串中位於索引值 i 和 j 上的字元交換。
如果你可以讓兩字串 s1 和 s2 變為相等,則回傳真(True);反之,則回傳假(False)。
限制:
n == s1.length == s2.length
1 ≦ n ≦ 10 ^ 5
s1 和 s2 只由小寫英文字母組成。
範例測資:
範例 1:
輸入: s1 = "abcdba", s2 = "cabdab"
輸出: true
解釋: 我們可以在 s1 上執行以下操作:
- 選擇索引值 i = 0 、 j = 2。結果為 s1 = "cbadba"。
- 選擇索引值 i = 2 、 j = 4。結果為 s1 = "cbbdaa"。
- 選擇索引值 i = 1 、 j = 5。結果為 s1 = "cabdab" = s2。
範例 2:
輸入: s1 = "abe", s2 = "bea"
輸出: false
解釋: 不可能讓兩字串相等。
解題思維:
可以看到由於 j - i 要是偶數的關係,導致奇數索引值與偶數索引值的字元不可能交換。
因此我們可以將 s1 和 s2 的字元各自根據索引值奇偶性來分類。而分完類後,可以看到在「同一類」中現在的 j - i 等價於每一個字元可以與「同一類」任意字元隨意交換位置。
而這表示著同一類字元中的任意排列組合都是可以達成的。
所以如果 s1 和 s2 的奇數索引值字元各自按字典序排序後一樣,並且 s1 和 s2 的偶數索引值字元各自按字典序排序後一樣,則 s1 可以變成與 s2 相同。反之,則不可能。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。