iT邦幫忙

0

【LeetCode練功坊】205, 1153題- 字串同構與字串變換

分享兩道字串的類似問題

同構字串

題目: 205. Isomorphic Strings
題意:
兩個字串s和t同構若s和t的字元有一一對應(one-to-one and onto)的關係,
判斷兩字串是否同構。
(可假設input s, t的長度一定一樣)

例子:

Input: s = "paper", t = "title"
Output: true

思路: 用字典記錄s的字元對應到t的哪個字元,
檢查s相同的字元對應到t相同的字元(不會出現aa -> cd的關係,確保onto,否則a對應到cd會沒有字對應)
取set()函數可以去除重複,判斷s, t相異的字元是否數量相同,以確保one-to-one的關係(不會有兩個s的不同字元對應到t的同一個字元,如ab -> zz)

程式:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        assert len(s)==len(t)
        cor={}
        for i, e in enumerate(s):
            if e not in cor:
                cor[e]=t[i]
            elif cor[e]!=t[i]:
                return False
        return len(set(s))==len(set(t))

字串變換

題目: 1153. String Transforms Into Another String (lock的題)
題意:
此題與205題的同構字串非常相似,
但需注意題目描述有所不同。
(假設input str1, str2 的長度一定一樣)

此題說有str1, str2兩個字串(只含小寫字母),
能否透過一系列的「換字」使得str1 變成 str2。
合法的換字動作為選擇一個小寫字母,
將str1所有該字母一起換成任一個小寫字母。

例: str1 = "aabcc", str2 = "ccdee"
可以先把c換成e,b換成d,a換成c即可成功,
但注意「換字順序」會有影響,
比如說若a先換成c,str1變成"ccbcc",則無法順利換成"ccdee"
注意在「同構字串」那題一定要one-to-one, onto才可以,
但本題只要「onto」就可以。

例如str1 = "ab", str2 = "aa" 可以把b換成a。

再看一例:
str1 = "abcdefghijklmnopqrstuvwxyz"
str2 = "bcdefghijklmnopqrstuvwxyzq"
目前有「onto」關係,
a~y需換成b~z,z要換成q,順序怎麼做?
可以先把z換成p,
然後再y換z,x換y,…,依序換過去即可

唯一有一種狀況雖然one-to-one, onto,是同構字串,但是會換字失敗,
就是str2 有全部26個小寫字母,使得str1沒有多餘的空間換字,
例如:
str1 = "abcdefghijklmnopqrstuvwxyz"
str2 = "bcdefghijklmnopqrstuvwxyza"
此時不論str1先換哪個字都只剩25個字母,換字失敗。

但是要記得排除一個例外中的例外,
例如:
str1 = "abcdefghijklmnopqrstuvwxyz"
str2 = "abcdefghijklmnopqrstuvwxyz"
str2 有全部26個小寫字母,
但是str1, str2原本就相同,根本不需要換(算True),
所以先判斷if str1==str2: return True

程式: (由於題目鎖住,給例子可在自己的開發環境上測試)

def canConvert(str1: str, str2: str) -> bool:
    if str1==str2: 
        return True
    cor={}
    for i,e in enumerate(str1):
        if e not in cor:
            cor[e]=str2[i]
        elif cor[e]!=str2[i]:
            return False
    return len(set(str2))<26


print(canConvert("ab","aa")) #True
print(canConvert("egg","add")) #True
print(canConvert("foo","bar")) #False
print(canConvert("paper","title")) #True
str1 = "abcdefghijklmnopqrstuvwxyz"
str2 = "bcdefghijklmnopqrstuvwxyzq"
print(canConvert(str1,str2)) #True

尚未有邦友留言

立即登入留言