LeetCode每日一题(2531. Make Number of Distinct Characters Equal)

You are given two 0-indexed strings word1 and word2.

A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].

Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.

Example 1:

Input: word1 = “ac”, word2 = “b”
Output: false

Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.

Example 2:

Input: word1 = “abcc”, word2 = “aab”
Output: true

Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = “abac” and word2 = “cab”, which both have 3 distinct characters.

Example 3:

Input: word1 = “abcde”, word2 = “fghij”
Output: true

Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.

Constraints:

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

速度不怎么理想但是好在思路比较直观 就是分别把 word1 和 word2 中的字母频次统计出来 然后把 word1 中的 a-z 与 word2 中的 a-z 进行交换

use std::collections::HashMap;

impl Solution {
    pub fn is_it_possible(word1: String, word2: String) -> bool {
        let mut m1 = word1.chars().fold(HashMap::new(), |mut m, c| {
            *m.entry(c).or_insert(0) += 1;
            m
        });
        let mut m2 = word2.chars().fold(HashMap::new(), |mut m, c| {
            *m.entry(c).or_insert(0) += 1;
            m
        });
        for c1 in 'a'..='z' {
            if let Some(count1) = m1.remove(&c1) {
                for c2 in 'a'..='z' {
                    if let Some(count2) = m2.remove(&c2) {
                        if count1 > 1 {
                            m1.insert(c1, count1 - 1);
                        }
                        *m1.entry(c2).or_insert(0) += 1;
                        if count2 > 1 {
                            m2.insert(c2, count2 - 1);
                        }
                        *m2.entry(c1).or_insert(0) += 1;
                        if m1.len() == m2.len() {
                            return true;
                        }
                        let count12 = m1.remove(&c2).unwrap();
                        if count12 > 1 {
                            m1.insert(c2, count12 - 1);
                        }
                        let count21 = m2.remove(&c1).unwrap();
                        if count21 > 1 {
                            m2.insert(c1, count21 - 1);
                        }
                        *m2.entry(c2).or_insert(0) += 1;
                    }
                }
                *m1.entry(c1).or_insert(0) += 1;
            }
        }
        false
    }
}