字符串

最长回文子串

1. 题目

已知一个只包含大小写的字符串，求用该字符串可以生成的最长回文子串的长度。

2. 思路

首先要考虑回文字符串的性质：当字符个数为奇数时，左右关与某个字符对称，当字符个数为偶数时左右对称。为此可以想到如果在字符串中有奇数个某字符可以去掉一个该字符使用剩下的偶数个来构成回文字符串，如果某个字符在字符串中有偶数个可以直接用来构成回文串。最后如果字符有剩余，可直接从中取一个字符作为中间字符，这样得到的回文子串最长。

3. 代码实现

int longestPalindrome(std::string str)
{
        char charMap[128] = {0};  // 字符串哈希表
        int max_length = 0;
        int flag = 0;

        for (int i = 0; i < str.size(); i++) {
            charMap[str[i]]++;
        }
        for (int i = 0; i < 128; i++) {
            if (charMap[i] % 2 == 0) {
                max_length += charMap[i];
            }
            else {
                max_length += charMap[i] - 1;
                flag = 1;
            }
        }
        return max_length + flag;
}

词语模式

1. 题目

给定一个字符串和一个匹配模式，如str = “dog dog great great"和匹配字符串pattern = "aabb"，那么成str和pattern匹配，确认给定的字符串和匹配模式是否匹配。

2. 思路

首先，从字符串中将单词拆解，在拆解的过程中同时对pattern进行map映射，并维护一个used数组用来判断pattern中的字符是否已经使用过了。
在拆解的过程中，

• 如果拆解的单词在map中没有出现过，那么判断当前的pattern对应的字符是否使用过，如果使用过就返回false，如果没有使用就将该单词做映射。
• 如果当前拆解出的单词出现过，判断pattern是否匹配，不匹配就返回false

3. 代码

bool wordPattern(std::string pattern, std::string str)
{
    std::map<std::string, char> word_map;  // 单词到pattern的映射表
    char used[128] = {0};
    std::string word;  // 临时保存拆分出来的单词
    int pos = 0;  // 指向pattern
    str.push_back(' ');

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == ' ') {  // 遇到空格说明遇到了单词
            if (pos == pattern.length()) {  // 到达pattern末尾
                return false;
            }
            // 若单词未出现在哈希映射中
            if (word_map.find(word) == word_map.end()) {
                if (used[pattern[pos]]) {  // 如果当前pattern字符已经使用
                    return false;
                }
                word_map[word] = pattern[pos];
                used[pattern[pos]] = 1;
            }
            else {
                if (word_map[word] != pattern[pos]) {
                    return false;
                }
            }
            word = "";
            pos++;
        }
        else {
            word +=str[i];
        }
    }
    if (pos != pattern.length()) {
        return false;
    }
    return true;
}

同字符词语分组

1. 题目

已知一组字符串，将其中相同字符组成的单词放在一起输出.

2. 思路

得到一个单词时候，对该单词进行排序然后用排序后的单词作为键，将原始的单词作为值进行hash存储，遇到下一个单词的时候，对单词进行排序判断是否在map中出现过，如果没有则添加新的键，如果存在就直接将该单词添加到该键所对应的值数组里面。

3. 代码

std::vector<std::vector<std::string>> groupAnagram(std::vector<std::string> &strs)
{
    std::map<std::string, std::vector<std::string>> mymap;  //  临时的map
    std::vector<std::vector<std::string>> res;
    // 遍历字符串向量
    for (auto i : strs) {
        std::string temp = i;
        std::sort(temp.begin(), temp.end());
        if (mymap.find(temp) == mymap.end()) {  // 如果在map中
            std::vector<std::string> item;
            mymap[temp] = item;
        }
        mymap[temp].push_back(i);
    }
    // 将hash表中的数据，放入res结果中
    for (auto i: mymap) {
        res.push_back(i.second);
    }

    return res;
}

无重复字符的最长子串

1. 题目

求给定的字符串中，无重复字符的最长子串

2. 思路

考虑在一次遍历的过程中能够得到想要的结果，此时需要使用两个指针，维护一个滑动窗口，窗口中的字符串即为我们要求的最长子串。这时问题就变成了怎么维护这个滑动窗口，两个指针分别在什么时候移动，怎么移动；

3. 代码

int lengthOfLongestSubStirng(std::string str)
{
    int begin = 0;
    int result = 0;
    std::string word = "";
    int char_map[128] = {0};

    for (int i = 0; i < str.size(); i++) {
        char_map[str[i]]++;
        if (char_map[str[i]] == 1) {  // word中没有出现过该字符
            word += str[i];
            if (result < word.length()) {
                result = word.length();
            }
        }
        else {  // 如果在word中出现过
            while (begin < i && char_map[str[i]] > 1) {
                char_map[str[begin]]--;
                begin++;
            }
            word = "";
            for (int j = begin; j <= i; j++) {
                word += str[j];
            }
        }

    }
    return result;
}