今天是 3 个跟字符串相关的题目。

387. First Unique Character in a String

Analysis

找出第一个字符串中第一个出现且只出现过一次的字符。

Code

直接散列。

class Solution {
public:
    int firstUniqChar(string s) {
        int times[26] = {0};
        for(auto ch: s) {
            times[ch - 'a']++;
        }
        for(int i = 0; i < s.length(); i++) {
            if(times[s[i] - 'a'] == 1) return i;
        }
        return -1;
    }
};

383. Ransom Note

Analysis

判断 ransomNote 这个字符串是否能被 magazine 这个字符串中的字符组成。

Code

直接散列，跟上个题差不多的思路。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(magazine.length() < ransomNote.length()) return false;
        int times[26] = {0};
        for(auto ch: magazine) {
            times[ch - 'a']++;
        }
        for(auto ch: ransomNote) {
            times[ch - 'a']--;
            if(times[ch - 'a'] < 0) return false;
        }
        return true;
    }
};

242. Valid Anagram

Analysis

这个题跟上个题也是类似的...

Code

method 1

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        vector<int> count1(26), count2(26);
        for(auto ch: s) {
            count1[ch - 'a']++;
        }
        for(auto ch: t) {
            count2[ch - 'a']++;
        }
        if(count1 == count2) return true;
        else return false;
    }
};

直接比较 vector 的骚操作忘记是从哪里学的了，当然也可以采取与上一题一样的思路，出现负数就返回 false。
还有一个进阶提示：如果输入的是 Unicode 字符怎么办？
要解决这个问题，首先需要知道的是 Unicode 与 Ascii 的不同。当然，不同点很多，但是在这个题目的背景下，只需要注意 Unicode 字符占 2 个字节，而 Ascii 只占 1 个字节。那么，如果还想用哈希的思路来解决这个问题，就需要对哈希表的 key 进行修改。不过，C++ 有现成的 map，所以直接用 map 就行了。

method 2

不过，只是解决这个题的话，其实还有一种做法，那就是排序，只要排序后的 2 个字符串一样，那就是符合条件的。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

Summary

这 3 个字符串处理的题，都比较简单...