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

更新於 發佈於 閱讀時間約 6 分鐘

題目敘述

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

第一個是指定順序的字串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

avatar-img
94會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!

































































題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
題目敘述 題目會給定一個參數n代表人口總數,和對應的信任關係陣列trust,陣列元素都是pair都以,[a, b]的形式呈現,代表a信任b。 要求我們找出法官是誰,返回法官的ID? 成為法官的條件: 1.每個人(除了法官自己之外)都信任法官。 2.法官不信任別人。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
題目敘述 題目會給定我們輸入邊長陣列nums,請問我們從裡面能夠建構出來的多邊形的最大周長是多少? 如果無解,返回-1 題目的原文敘述 約束條件 Constraints: 3 <= n <= 10^5 輸入陣列長度nums介於3 ~ 十萬 之間。 1 <= nums[i] <=
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
題目敘述 題目會給定一個參數n代表人口總數,和對應的信任關係陣列trust,陣列元素都是pair都以,[a, b]的形式呈現,代表a信任b。 要求我們找出法官是誰,返回法官的ID? 成為法官的條件: 1.每個人(除了法官自己之外)都信任法官。 2.法官不信任別人。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
題目敘述 題目會給定我們輸入邊長陣列nums,請問我們從裡面能夠建構出來的多邊形的最大周長是多少? 如果無解,返回-1 題目的原文敘述 約束條件 Constraints: 3 <= n <= 10^5 輸入陣列長度nums介於3 ~ 十萬 之間。 1 <= nums[i] <=
你可能也想看
Google News 追蹤
Thumbnail
希望透過條列和簡介,可以更方便讀者選讀自己偏好的主題。
Thumbnail
題目敘述 Kth Distinct String in an Array 給定一個輸入陣列arr 和 參數k 請返回第k個出現恰好一次的陣列元素。
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Sort the Jumbled Numbers 給定兩個輸入陣列 第一個是映射表,提供0~9 mapping到新數字的映射關係。 第二個陣列是原始數值。 請重新排序原始數值,排序依據是根據映射表對應之後的新數值的大小決定。 如果對應之後的新數值大小相同,則由原本的前後相對順序決定。
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄕ。
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄔ。
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄎ和ㄏ。
Thumbnail
在比賽裡這就是大家拚手速的題目了,準備好了嗎?
Thumbnail
題目敘述 題目會給定我們兩個字串。 第一個是指定順序的字串order。 第二個是輸入字串s。 要求我們依據order給定的順序,重新排列s。 如果出現order中沒有出現的字母,任意位置皆可。 合法答案可能不只一組,輸出其中一種即可。 題目的原文敘述 測試範例 Example
Thumbnail
希望透過條列和簡介,可以更方便讀者選讀自己偏好的主題。
Thumbnail
題目敘述 Kth Distinct String in an Array 給定一個輸入陣列arr 和 參數k 請返回第k個出現恰好一次的陣列元素。
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Sort the Jumbled Numbers 給定兩個輸入陣列 第一個是映射表,提供0~9 mapping到新數字的映射關係。 第二個陣列是原始數值。 請重新排序原始數值,排序依據是根據映射表對應之後的新數值的大小決定。 如果對應之後的新數值大小相同,則由原本的前後相對順序決定。
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄕ。
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄔ。
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
以注音為排序標準,範圍為N5-N3的日語漢字筆記。 本次排序為ㄎ和ㄏ。
Thumbnail
在比賽裡這就是大家拚手速的題目了,準備好了嗎?
Thumbnail
題目敘述 題目會給定我們兩個字串。 第一個是指定順序的字串order。 第二個是輸入字串s。 要求我們依據order給定的順序,重新排列s。 如果出現order中沒有出現的字母,任意位置皆可。 合法答案可能不只一組,輸出其中一種即可。 題目的原文敘述 測試範例 Example