字典應用: 客製化字串排序 Custom Sort String_Leetcode #791

Brett Jordan on Unsplash

題目敘述

題目會給定我們兩個字串。

第一個是指定順序的字串order。
第二個是輸入字串s。

要求我們依據order給定的順序，重新排列s。
如果出現order中沒有出現的字母，任意位置皆可。

合法答案可能不只一組，輸出其中一種即可。

題目的原文敘述

測試範例

Example 1:

Input:  order = "cba", s = "abcd"

Output:  "cbad"

Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Example 2:

Input:  order = "bcafg", s = "abcd"

Output:  "bcad"

Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.

Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "bacd" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

約束條件

Constraints:

• 1 <= order.length <= 26

字串order的長度介於1~26之間。

• 1 <= s.length <= 200

字串s的長度介於1~200之間。

• order and s consist of lowercase English letters.

字串order 和 字串s都只會有小寫英文字母。

• All the characters of order are unique.

order內部的字元都是獨一無二的，不會重複。

演算法 字典 + 重新串接英文字母

先針對s建造一個字典，統計字串s每個英文字母的出現次數。

接著，依據order給定的順序，和剛剛得到s的英文字母的出現次數，
重新串接每個英文字母。

接著，針對沒有定義到，也就是order以外的英文子母，重新串接到輸出結果的尾端。

程式碼 字典 + 重新串接英文字母

class Solution:
    def customSortString(self, order: str, s: str) -> str:

        result = ""
        
        ## Dictionary
        # key: lowercase English letters
        # value: occurrence
        occ = Counter(s)

        # Rearrange letters with the given order
        for char in order:
            if char in occ:
                result += char * occ[char]
                del occ[char]

        # Padding remainging letters outside order
        for char, count in occ.items():
            result += char * count

        return result

複雜度分析 字典 + 重新串接英文字母

時間複雜度:

依序掃描字串s和字串order，所需時間為O(s) + O( order )

空間複雜度:

建立一個字典，所需空間為O(26) = O(1)，因為題目以定義字串內都是小寫英文字母，本題可視為使用常數空間。

關鍵知識點

依據order給定的順序，和剛剛得到s的英文字母的出現次數，重新串接每個英文字母。

需要s的英文字母的出現次數最為輔助資訊，聯想到python dictionary
(字典，相當於資料結構裡的雜湊映射表)。

Reference:

[1] Custom Sort String - LeetCode