前往
大廳
主題

LeetCode - 1528. Shuffle String 解題心得

Not In My Back Yard | 2023-03-02 12:00:01 | 巴幣 100 | 人氣 190

題目連結:


題目意譯:
你被給定一字串 s 以及一整數陣列 indices,兩者長度相同。字串 s 中的字元將被重新排列使得原先位於索引值 i 的字元將移動到索引值 indices[i] 的位置。

回傳重新排列後的字串。

限制:
s.length == indices.length == n
1 ≦ n ≦ 100
s 只由小寫英文字母組成。
0 ≦ indices[i] < n
indices 中的數值彼此相異。



範例測資:
範例 1:
輸入: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
輸出: "leetcode"
解釋: 如上所示,"codeleet" 重新排列後變成了 "leetcode"。

範例 2:
輸入: s = "abc", indices = [0,1,2]
輸出: "abc"
解釋: 重新排列後,每個字元維持在相同的地方。


解題思維:
雖然可以直接生成一個長度與 s 相同的字串,然後把每個 s[i] 放到對應的 indices[i] 的位置。最後再回傳該字串即可。

不過也可以直接在 s 上原地(In-place)地把重新排列後的字串生成出來:
掃過字串 s,每遇到一次 indices[i] ≠ i 時,就表示 s[i] 現在的位置是錯的,應該與 s[indices[i]] 這個字元互換位置後 s[i] 才會是對的位置。

因此我們可以先把 s[i] 與 s[indices[i]] 兩字元交換,然後把 indices[i] 與 indices[indices[i]] 兩個索引值交換(因為對應位置的字元交換了,理所當然索引值要跟著動)。

接著如果此時 indices[i] 依舊不等於 i(此時的 indices[i] 是「原先的」indices[indices[i]]),就重複以上步驟;反之,就看下一個字元 s[i + 1] 是否在「正確的位置」。

掃完之後便可以確保所有字元在「正確的位置」,因此此時的 s 即為所求。




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

創作回應

更多創作