Leetcode

Leetcode.242.Valid Anagram

2019-12-09  本文已影响0人  Jimmy木

题目

给出两个字符串,判断字符串是否是颠倒顺序的字符串。

Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false

思路1

如果只包含小写字母,就固定序号0-25为26个小写字母,通过数组计算出现次数进行对比。

bool isAnagram(string s, string t) {
    vector<int> vec1(26, 0);
    vector<int> vec2(26, 0);
    if (s.size() != t.size()) {
        return false;
    }
    for (int i = 0; i < s.size(); i++) {
        vec1[s[i]-'a']++;
        vec2[t[i]-'a']++;
    }

    for (int i = 0;i < 26;i++) {
        if (vec1[i] != vec2[i]) {
            return false;
        }
    }
    return true;
}

思路2

如果不是小写字母,就辅助一个map记录数组的索引。

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) {
        return false;
    }
    vector<int> vec1(s.size(),0);
    vector<int> vec2(t.size(),0);
    unordered_map<char, int> m_map;

    for (int i = 0; i < s.size(); i++) {
        if (m_map.count(s[i]) == 0) {
            m_map[s[i]] = (int)m_map.size();
        }
        vec1[m_map[s[i]]]++;
    }
    for (int i = 0; i < t.size(); i++) {
        if (m_map.count(t[i]) == 0) {
            return false;
        }
        vec2[m_map[t[i]]]++;
    }
    for (int i = 0;i < m_map.size();i++) {
        if (vec1[i] != vec2[i]) {
            return false;
        }
    }

    return true;
}

总结

熟练掌握各种基础数据结构。

上一篇下一篇

猜你喜欢

热点阅读