字串應用題 最少需要幾個步驟讓兩個字串變成"同字母異序詞" Leetcode #1347

字串應用題 最少需要幾個步驟讓兩個字串變成"同字母異序詞" Leetcode #1347

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

題目敘述

題目會給我們兩個字串作為輸入,分別是字串s和字串t,問我最少要做幾次字元轉換,讓字串t和字串s成為Anagram"同字母異序詞"?

註: 例如 god 和 dog 就是 Anagram 同字母異序詞,也是就說,組成字母相同,但是順序可以重新排列。

題目的原文敘述


測試範例

Example 1:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.
把字串t中的一個a改成b,字串​s和字串t就是Anagram 同字母異序詞

Example 2:

Input: s = "leetcode", t = "practice"
Output: 5
Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.

Example 3:

Input: s = "anagram", t = "mangaar"
Output: 0
Explanation: "anagram" and "mangaar" are anagrams.
不用特別調整​,原本就是Anagram同字母異序詞

約束條件

Constraints:

  • 1 <= s.length <= 5 * 10^4

字串s的長度介於1~5*10^4之間。

  • s.length == t.length

字串s的長度 = 字串t的長度。

  • s and t consist of lowercase English letters only.

字串s和字串t裡面只會有小寫英文字母。


演算法

其實依照定義出發即可。

這題的目標是讓兩個字串成為Anagram 同字母異序詞,

關鍵就在於,每個曾經出現的英文字母的出現次數必須相同。

到這邊,可以很直覺的聯想到用字典dictionary(或者稱 雜湊映射表Hash table)來實作。

建立兩個字典s_occ_dict,t_occ_dict分別統計兩個字串各自的字母出現次數。

然後,計算出現次數差值的絕對值總和,每做一次字元轉換,就代表有一個舊字元減少出現一次,一個新字元多出現一次,一來一回等於重複計算,最後再除以2,扣掉重複的部分,就是所需字元轉換的次數的最小值。


程式碼

from collections import defaultdict
from string import ascii_lowercase

class Solution:
def minSteps(self, s: str, t: str) -> int:

# dictionary
# key : alphabet letter
# value : occurrence
s_occ_dict = defaultdict( int )
t_occ_dict = defaultdict( int )

# build the dictionary for input string s
for ch in s:
s_occ_dict[ch] += 1

# build the dictionary for input string t
for ch in t:
t_occ_dict[ch] += 1


# counting the minimum distance to anagram
diff = 0

for ch in ascii_lowercase:

diff += abs(s_occ_dict[ch] - t_occ_dict[ch])

return diff//2


關鍵知識點

這題的目標是讓兩個字串成為Anagram 同字母異序詞,

關鍵就在於,每個曾經出現的英文字母的出現次數必須相同。

到這邊,可以很直覺的聯想到用字典dictionary(或者稱 雜湊映射表Hash table)來實作。


複雜度分析

時間複雜度:

從頭到尾掃描過每個字元,所需時間為O(n) = O(字串長度)

空間複雜度:

因為題目已經給了一個很強的條件,字串s和字串t裡面只會有小寫英文字母,所以字典的大小最大就是統計每個小寫字母的出現次數=O(26)=O(1) 常數級別


Reference:

[1] Minimum Number of Steps to Make Two Strings Anagram - LeetCode

avatar-img
小松鼠的演算法樂園
95會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 問我們任意祖先節點和晚輩節點之間,最大的差值的絕對值是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Ou
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 並且給定感染的病毒源節點位置,每個單位時間,可以向相鄰的節點感染一次,問我們需要多少時間去感染整棵樹? 題目的原文敘述 測試範例 Example 1: Input: root = [1,5,3,null,4,10,6,
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table:
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 問我們任意祖先節點和晚輩節點之間,最大的差值的絕對值是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Ou
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 並且給定感染的病毒源節點位置,每個單位時間,可以向相鄰的節點感染一次,問我們需要多少時間去感染整棵樹? 題目的原文敘述 測試範例 Example 1: Input: root = [1,5,3,null,4,10,6,
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table: