題目敘述
題目會給定我們兩個字串word1 和 word2。
允許我們不限制次數進行下列兩種操作:
- 任意調換其中兩個字元的位置。
- 把字串中的某個字元全部置換成另一個字元，同時把另一個字元同時置換成某個字元。(例如把字串中原本的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之間。
word1andword2contain only lowercase English letters.
word1和word2都只包含小寫英文字母。
演算法
這題的關鍵在於找出兩個字串在置換和字元替換後，可以相等的條件是什麼?
- 出現的字元集合必須相同，例如word1有出現a,b,c,d 那麼word2也必須有出現a,b,c,d
因為，如果出現的字元集合不同，不管怎麼替換，一定會有多餘的字元留下來，註定無法讓兩個字串相等。
- 出現次數的序列在重新排序之後必須相等，例如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代表兩個字串可以透過替換和置換換到相同的字元排列，使兩個字串相等。
因為，如果出現次數的序列在重新排列之後不同，代表一定會有某個字元必定出現次數不均等，造成兩個字串不管怎麼置換或替換字元都不可能相等。
