字串應用題 判定兩個字串是否接近(Close) Leetcode #1657 精選75

Nathan Dumlao on Unsplash

題目敘述

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

允許我們不限制次數進行下列兩種操作:

1. 任意調換其中兩個字元的位置。
2. 把字串中的某個字元全部置換成另一個字元，同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b，把原本的b都換成a)

問我們能不能通過上述兩項操作，讓word1, word2兩個字串相等?

如果可以，返回True

如果不行，返回False

題目的原文敘述

測試範例

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

約束條件

Constraints:

• 1 <= word1.length, word2.length <= 10^5

word1和word2的字串長度都介於1~10^5之間。

• word1 and word2 contain only lowercase English letters.

word1和word2都只包含小寫英文字母。

演算法

這題的關鍵在於找出兩個字串在置換和字元替換後，可以相等的條件是什麼?

1. 出現的字元集合必須相同，例如word1有出現a,b,c,d 那麼word2也必須有出現a,b,c,d

因為，如果出現的字元集合不同，不管怎麼替換，一定會有多餘的字元留下來，註定無法讓兩個字串相等。

2. 出現次數的序列在重新排序之後必須相等，例如word1的a,b,c,d分別出現1,2,3,4次，word2的a,b,c,d分別出現4,3,2,1次，雖然原始的出現次數不同，分別是1,2,3,4和4,3,2,1。但是，兩者重新排序後，皆為1,2,3,4代表兩個字串可以透過替換和置換換到相同的字元排列，使兩個字串相等。

因為，如果出現次數的序列在重新排列之後不同，代表一定會有某個字元必定出現次數不均等，造成兩個字串不管怎麼置換或替換字元都不可能相等。