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

Edho Pratama on Unsplash

題目敘述

題目會給我們兩個字串作為輸入，分別是字串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