題目連結:
題目意譯:
你被給定一字串 s 以及一整數 k,你可以從 s 的前 k 個字母中選一個將其移至字串結尾。
回傳經由套用以上操作若干次後可以產生的最小字典序之字串。
限制:
1 ≦ k ≦ s.length ≦ 1000
s 由小寫英文字母組成。
範例測資:
範例 1:
輸入: s = "cba", k = 1
輸出: "acb"
解釋:
在第一步中,我們將第一個字元 'c' 移到結尾,得到字串 "bac"。
在第二步中,我們將第一個字元 'b' 移到結尾,得到字串 "acb"。
範例 2:
輸入: s = "baaca", k = 3
輸出: "aaabc"
解釋:
在第一步中,我們將第一個字元 'b' 移到結尾,得到字串 "aacab"。
在第二步中,我們將第三個字元 'c' 移到結尾,得到字串 "aaabc"。
解題思維:
首先觀察幾個例子之後,可能可以發現當 k ≧ 2 時,你能產生的最小字典序之字串即為字串中所有字元按字典序排序之結果。以下是直觀的說明:
當 k = 2 時,我們可以將 s[0] 移至任意的位置。
例如我們有 "aABCDEF",其中大寫字母代表目前不在乎的字元。而現在如果我們想要把 'a' 移動到 'B' 和 'C' 的中間。則我們可以:
選第二個字母丟到結尾,得
"aBCDEFA"
選第二個字母丟到結尾,得
"aCDEFAB"
選第一個字母丟到結尾,得
"CDEFABa"
選第一個字母丟到結尾,得
"DEFABaC"
選第一個字母丟到結尾,得
"EFABaCD"
選第一個字母丟到結尾,得
"FABaCDE"
選第一個字母丟到結尾,得
"ABaCDEF"
所以可以看到藉由以上方式:要移動到的位置的前面會有幾個字元,就移動幾次第二個字母到結尾;剩下的次數則是移動第一個字元。而這樣可以將 s[0] 移動到我們想要的位置,且不會更動其他字母之間的相對順序。
而 k > 2 時,利用與 k = 2 時一模一樣的策略即可。因此我們可以藉由這個方式把整個字串的字元按照字典序由小到大排序,因此該排序後的字串即是所求。
唯一的例外是 k = 1 時,這時我們只能窮舉所有可能的情況,看哪個是字典序最小的即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。