Percy's blog
0%

Determine if Two Strings Are Close

Posted on Edited on In

出處:

Leetcode Week 4: Jan. 22nd - Jan. 28th

題目:

給定兩字串，並根據以下兩條規則進行操作，則這兩字串視為密切相似的

  • 任意交換兩個 已存在的 字元，也就是說 abcde -> aecdb
  • 轉換任意 已存在的 的字元為另一個 以存在的 字元，也就是說 abbcd -> addcb (注意! 相同的字元都要做轉換)

給定兩字串 word1、word2，如果 word1 與 word2 是密切的(close)則回傳 true，否則回傳 false

範例1:

1
2
3
4
5
Input: word1 = "abc", word2 = "bca"
Output: true
理由: word1 經過兩次操作能變成 word2
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

範例2:

1
2
3
Input: word1 = "cabbba", word2 = "aabbcc"
Output: false
理由: word1 不可能變成 word2

限制:

  • 1 <= word1.length, word2.length <= 105

  • 字串 word1 及 word2 都只有小寫英文字母

解題:

條件1相對單純，這題主要判斷如何讓 操作2 的條件成立，其實只要去判斷兩字串中，字母分布率是否相同即可

也就是說，假如兩字串是 cabbba、abbccc，你會發現兩字串字母分布率相同，分別是 {“c”: 1, “b”: 3, “a”: 2} 及 {“c”: 3, “b”: 2, “a”: 1} (都是 1、2、3)；也可以加上一些判斷邏輯略過根本不需要計算分母分布率的情況

附上程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import 
class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False
        elif set(word1) != set(word2):
            return False
        word1\_dict = defaultdict(int)
        word2\_dict = defaultdict(int)
        
        for word in word1:
            word1\_dict\[word\] += 1
        
        for word in word2:
            word2\_dict\[word\] += 1

        if sorted(word1\_dict.values()) != sorted(word2\_dict.values()):
            return False
        
        return True

Reference:

  1. Determine if Two Strings Are Close