Java&C++题解与拓展——leetcode890.查找和替换模式【么的新知识】

• 题目要求
• 思路：哈希表模拟
• • Java
  • C++
  • Rust
• 总结

• 用哈希表 m a p map map存放当前单词与模板之间的映射关系，为了避免重复映射，维护一个 v i s vis vis表示已遍历过；
  • 字符集数量小（26个），所以用数组替代了。

class Solution {
    public List findAndReplacePattern(String[] words, String pattern) {
        List res = new ArrayList<>();
        int[] map = new int[26], vis = new int[26];
        for(String w : words) {
            Arrays.fill(map, -1);
            Arrays.fill(vis, 0);
            boolean match = true;
            for(int i = 0; i < pattern.length() && match; i++) {
                int cw = w.charAt(i) - 'a', cp = pattern.charAt(i) - 'a';
                if(map[cw] == -1 && vis[cp] == 0) {
                    map[cw] = cp; // cp映射为cw
                    vis[cp] = 1;
                }
                else if(map[cw] != cp)
                    match = false;
            }
            if(match)
                res.add(w);
        }
        return res;
    }
}

• 时间复杂度： O ( ∑ i = 0 n l e n ( w s [ i ] ) + n × C ) O(sum^n_{i=0}len(ws[i])+ntimes C) O(∑i=0n​len(ws[i])+n×C)，其中 C C C为字符集大小，即26.
• 空间复杂度： O ( C ) O(C) O(C)

class Solution {
public:
    vector findAndReplacePattern(vector& words, string pattern) {
        vector res;
        int map[26], vis[26];
        for(string w : words) {
            memset(map, -1, sizeof(map));
            memset(vis, 0, sizeof(vis));
            bool match = true;
            for(int i = 0; i < pattern.length() && match; i++) {
                int cw = w[i] - 'a', cp = pattern[i] - 'a';
                if(map[cw] == -1 && vis[cp] == 0) {
                    map[cw] = cp; // cp映射为cw
                    vis[cp] = 1;
                }
                else if(map[cw] != cp)
                    match = false;
            }
            if(match)
                res.push_back(w);
        }
        return res;
    }
};

• 时间复杂度： O ( ∑ i = 0 n l e n ( w s [ i ] ) + n × C ) O(sum^n_{i=0}len(ws[i])+ntimes C) O(∑i=0n​len(ws[i])+n×C)，其中 C C C为字符集大小，即26.
• 空间复杂度： O ( C ) O(C) O(C)

• usize类型里似乎不能识别负号，所以就搞了个99替代。

impl Solution {
    pub fn find_and_replace_pattern(words: Vec, pattern: String) -> Vec {
        let mut res = Vec::new();
        for w in words {
            let(mut map, mut vis, mut MATCH) = (vec![0; 26], vec![0; 26], true);
            for i in 0..26 {
                map[i] = 99 as usize;
                vis[i] = 0 as usize;
            }
            for i in 0..w.len() {
                let cw = (w.as_bytes()[i] - 'a' as u8) as usize;
                let cp = (pattern.as_bytes()[i] - 'a' as u8) as usize;
                if map[cw] == 99 && vis[cp] == 0 {
                    map[cw] = cp; // cp 映射为cw
                    vis[cp] = 1;
                }
                else if map[cw] != cp {
                    MATCH = false;
                }
            }
            if MATCH {
                res.push(w);
            }
        }
        res
    }
}

• 时间复杂度： O ( ∑ i = 0 n l e n ( w s [ i ] ) + n × C ) O(sum^n_{i=0}len(ws[i])+ntimes C) O(∑i=0n​len(ws[i])+n×C)，其中 C C C为字符集大小，即26.
• 空间复杂度： O ( C ) O(C) O(C)

模拟题么的好总结……

学习了 R u s t Rust Rust的usize、u8乱七八糟的类型。