LeetCode 1657. Determine whether the two strings are close

1657. Determine whether two strings are close to

If you can use the following operations to get a string from one string to another , Two strings near ：

• operation 1： Exchange any two

  existing

  character .

  • for example ,a**b**cd**e** -> a**e**cd**b**

• operation 2： Will a

  existing

  Each occurrence of a character is converted to another

  existing

  character , And do the same thing for another character .

  • for example ,**aa**c**abb** -> **bb**c**baa**（ all a Turn into b , And all b Convert to a ）

You can use these two operations multiple times for any string you want .

Here are two strings ,word1 and word2 . If word1 and word2 near , Just go back to true ; otherwise , return false .

Example 1：

 Input ：word1 = "abc", word2 = "bca"
 Output ：true
 explain ：2  Operations from  word1  get  word2 .
 Perform the operation  1："abc" -> "acb"
 Perform the operation  1："acb" -> "bca"

Example 2：

 Input ：word1 = "a", word2 = "aa"
 Output ：false
 explain ： No matter how many operations are performed , I can't get it from  word1  obtain  word2 , vice versa .

Example 3：

 Input ：word1 = "cabbba", word2 = "abbccc"
 Output ：true
 explain ：3  Operations from  word1  get  word2 .
 Perform the operation  1："cabbba" -> "caabbb"
 Perform the operation  2："caabbb" -> "baaccc"
 Perform the operation  2："baaccc" -> "abbccc"

Example 4：

 Input ：word1 = "cabbba", word2 = "aabbss"
 Output ：false
 explain ： No matter how many operations are performed , I can't get it from  word1  obtain  word2 , vice versa .

Tips ：

• 1 <= word1.length, word2.length <= 105
• word1 and word2 Contains only lowercase English letters

Two 、 Method 1

automata

class Solution {
    
    public boolean closeStrings(String word1, String word2) {
    
        char[] arr = word1.toCharArray();
        char[] brr= word2.toCharArray();
        if (arr.length == brr.length) {
    
            int[] mark1 = new int[26];
            int[] mark2 = new int[26];
            for (char c : arr) {
    
                mark1[c - 'a']++;
            }
            for (char c : brr) {
    
                if (mark1[c - 'a'] == 0) {
    
                    return false;
                }
                mark2[c - 'a']++;
            } 
            Arrays.sort(mark1);
            Arrays.sort(mark2);
            for (int i = 0; i < mark1.length; i++) {
    
                if (mark1[i] != mark2[i]) {
    
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}

Complexity analysis

• Time complexity ：O(nlogn)..

• Spatial complexity ：O(n).