Question

1657. Determine if Two Strings Are Close

中文文档

Description

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
  • For example, abcde -> aecdb
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
  • For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true_ if _word1_ and _word2_ are close, and _false_ otherwise._

 

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 <= 105
• word1 and word2 contain only lowercase English letters.

Solutions

Solution 1: Counting + Sorting

According to the problem description, two strings are close if they meet the following two conditions simultaneously:

1. The strings word1 and word2 must contain the same types of letters.
2. The arrays obtained by sorting the counts of all characters in word1 and word2 must be the same.

Therefore, we can first use an array or hash table to count the occurrences of each letter in word1 and word2 respectively, and then compare whether they are the same. If they are not the same, return false early.

Otherwise, we sort the corresponding counts, and then compare whether the counts at the corresponding positions are the same. If they are not the same, return false.

At the end of the traversal, return true.

The time complexity is $O(m + n + C \times \log C)$, and the space complexity is $O(C)$. Here, $m$ and $n$ are the lengths of the strings word1 and word2 respectively, and $C$ is the number of letter types. In this problem, $C=26$.

class Solution:
  def closeStrings(self, word1: str, word2: str) -> bool:
    cnt1, cnt2 = Counter(word1), Counter(word2)
    return sorted(cnt1.values()) == sorted(cnt2.values()) and set(
      cnt1.keys()
    ) == set(cnt2.keys())

class Solution {
  public boolean closeStrings(String word1, String word2) {
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i = 0; i < word1.length(); ++i) {
      ++cnt1[word1.charAt(i) - 'a'];
    }
    for (int i = 0; i < word2.length(); ++i) {
      ++cnt2[word2.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if ((cnt1[i] == 0) != (cnt2[i] == 0)) {
        return false;
      }
    }
    Arrays.sort(cnt1);
    Arrays.sort(cnt2);
    return Arrays.equals(cnt1, cnt2);
  }
}

class Solution {
public:
  bool closeStrings(string word1, string word2) {
    int cnt1[26]{};
    int cnt2[26]{};
    for (char& c : word1) {
      ++cnt1[c - 'a'];
    }
    for (char& c : word2) {
      ++cnt2[c - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if ((cnt1[i] == 0) != (cnt2[i] == 0)) {
        return false;
      }
    }
    sort(cnt1, cnt1 + 26);
    sort(cnt2, cnt2 + 26);
    return equal(cnt1, cnt1 + 26, cnt2);
  }
};

func closeStrings(word1 string, word2 string) bool {
  cnt1 := make([]int, 26)
  cnt2 := make([]int, 26)
  for _, c := range word1 {
    cnt1[c-'a']++
  }
  for _, c := range word2 {
    cnt2[c-'a']++
  }
  if !slices.EqualFunc(cnt1, cnt2, func(v1, v2 int) bool { return (v1 == 0) == (v2 == 0) }) {
    return false
  }
  sort.Ints(cnt1)
  sort.Ints(cnt2)
  return slices.Equal(cnt1, cnt2)
}

function closeStrings(word1: string, word2: string): boolean {
  const cnt1 = Array(26).fill(0);
  const cnt2 = Array(26).fill(0);
  for (const c of word1) {
    ++cnt1[c.charCodeAt(0) - 'a'.charCodeAt(0)];
  }
  for (const c of word2) {
    ++cnt2[c.charCodeAt(0) - 'a'.charCodeAt(0)];
  }
  for (let i = 0; i < 26; ++i) {
    if ((cnt1[i] === 0) !== (cnt2[i] === 0)) {
      return false;
    }
  }
  cnt1.sort((a, b) => a - b);
  cnt2.sort((a, b) => a - b);
  return cnt1.join('.') === cnt2.join('.');
}

impl Solution {
  pub fn close_strings(word1: String, word2: String) -> bool {
    let mut cnt1 = vec![0; 26];
    let mut cnt2 = vec![0; 26];
    for c in word1.chars() {
      cnt1[((c as u8) - b'a') as usize] += 1;
    }
    for c in word2.chars() {
      cnt2[((c as u8) - b'a') as usize] += 1;
    }
    for i in 0..26 {
      if (cnt1[i] == 0) != (cnt2[i] == 0) {
        return false;
      }
    }
    cnt1.sort();
    cnt2.sort();
    cnt1 == cnt2
  }
}