題目連結:
題目意譯:
你被給定一個英數字串 s。(英數字串為一個由小寫英文字母與數字組成的字串)。
你需要找到一個字串的排列方式其中沒有字母接著另一字母且沒有數字接著另一數字。也就是說,沒有兩個相鄰的字元是同一個種類。
回傳重新排列後的字串;如果不可能將字串重新排列符合格式,則回傳一個空字串。
限制:
1 ≦ s.length ≦ 500
s 只由小寫英文字母和數字所組成。
範例測資:
範例 1:
輸入: s = "a0b1c2"
輸出: "0a1b2c"
解釋: 在 "0a1b2c" 中沒有兩個相鄰字元是同一種類。"a0b1c2" 、 "0a1b2c" 和 "0c2a1b" 同時也是合法的排列。
範例 2:
輸入: s = "leetcode"
輸出: ""
解釋: "leetcode" 只有字母,所以我們無法把它們用數字分隔開來。
範例 3:
輸入: s = "1229857369"
輸出: ""
解釋: "1229857369" 只有數字,所以我們無法把它們用字母分隔開來。
解題思維:
掃過一次 s 來統計有多少字母(假設為 L 個)以及有多少個數字(假設有 D 個)。
而如果 |L - D| > 1,則代表我們無法用字母與數字交錯來分開彼此。因此直接回傳空字串 "" 即可。
而如果 |L - D| ≦ 1,則再判斷 L 比較大或是 D 比較大。如果 L 比較大,則我們需要把數字們塞在兩兩字母之間;如果 D 比較大,則我們需要把字母們塞在兩兩數字之間;而 L 等於 D,則隨便選其中一種方式,只要交錯即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。