[閒聊] 每日leetcode 75 - Day8 - 6

[yam276 (史萊哲林的優等生)]

1657. Determine if Two Strings Are Close


題目：

你可以用兩種操作

1. 隨意更換字元順序

2. 把字串內兩種符號種類對換

看能不能用他們把兩個字串變成一樣的


思路：

操作一其實沒意思 不用考慮 因為操作次數無限

重點還是操作二


操作二這樣寫

代表只要兩個字串的字元 freq 一樣

字元種類也一樣 沒有一個有一個沒有的

就可以變換


最簡單的方法

可以用 HashMap 蒐集次數

用 HashSet 比較字母

用 Vec sort 比較 freq


但這樣時間複雜度不夠高

更高的還是創 26 大小字母陣列來解


Code:

use std::collections::{HashMap, HashSet};
impl Solution {
    pub fn close_strings(word1: String, word2: String) -> bool {
        let mut freq1 = HashMap::new();
        let mut freq2 = HashMap::new();

        for c in word1.chars() {
            *freq1.entry(c).or_insert(0) += 1;
        }

        for c in word2.chars() {
            *freq2.entry(c).or_insert(0) += 1;
        }

        let set1: HashSet<_> = freq1.keys().cloned().collect();
        let set2: HashSet<_> = freq2.keys().cloned().collect();

        if set1 != set2 {
            return false;
        }

        let mut count1: Vec<_> = freq1.values().cloned().collect();
        let mut count2: Vec<_> = freq2.values().cloned().collect();

        count1.sort();
        count2.sort();

        if count1 != count2 {
            return false;
        }

        true
    }
}


26 字元陣列版：

impl Solution {
    pub fn close_strings(word1: String, word2: String) -> bool {
        let mut count1 = [0; 26];
        let mut count2 = [0; 26];
        let mut set1 = [false; 26];
        let mut set2 = [false; 26];

        for c in word1.chars() {
            let i = (c as u8 - b'a') as usize;
            count1[i] += 1;
            set1[i] = true;
        }

        for c in word2.chars() {
            let i = (c as u8 - b'a') as usize;
            count2[i] += 1;
            set2[i] = true;
        }

        if set1 != set2 {
            return false;
        }

        let mut freq1: Vec<_> = count1.iter()
                                      .filter(|&&x| x > 0)
                                      .cloned().collect();

        let mut freq2: Vec<_> = count2.iter()
                                      .filter(|&&x| x > 0)
                                      .cloned().collect();


        freq1.sort();
        freq2.sort();

        freq1 == freq2
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749542762.A.637.html