最長回文子串

1. 題目

已知一個只包含大小寫的字符串，求用該字符串可以生成的最長回文子串的長度。

2. 思路

首先要考慮回文字符串的性質(zhì)：當(dāng)字符個數(shù)為奇數(shù)時，左右關(guān)與某個字符對稱，當(dāng)字符個數(shù)為偶數(shù)時左右對稱。為此可以想到如果在字符串中有奇數(shù)個某字符可以去掉一個該字符使用剩下的偶數(shù)個來構(gòu)成回文字符串，如果某個字符在字符串中有偶數(shù)個可以直接用來構(gòu)成回文串。最后如果字符有剩余，可直接從中取一個字符作為中間字符，這樣得到的回文子串最長。

3. 代碼實現(xiàn)

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匹配，確認(rèn)給定的字符串和匹配模式是否匹配。

2. 思路

首先，從字符串中將單詞拆解，在拆解的過程中同時對pattern進(jìn)行map映射，并維護(hù)一個used數(shù)組用來判斷pattern中的字符是否已經(jīng)使用過了。
在拆解的過程中，

• 如果拆解的單詞在map中沒有出現(xiàn)過，那么判斷當(dāng)前的pattern對應(yīng)的字符是否使用過，如果使用過就返回false，如果沒有使用就將該單詞做映射。
• 如果當(dāng)前拆解出的單詞出現(xiàn)過，判斷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()) {  // 到達(dá)pattern末尾
                return false;
            }
            // 若單詞未出現(xiàn)在哈希映射中
            if (word_map.find(word) == word_map.end()) {
                if (used[pattern[pos]]) {  // 如果當(dāng)前pattern字符已經(jīng)使用
                    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. 思路

得到一個單詞時候，對該單詞進(jìn)行排序然后用排序后的單詞作為鍵，將原始的單詞作為值進(jìn)行hash存儲，遇到下一個單詞的時候，對單詞進(jìn)行排序判斷是否在map中出現(xiàn)過，如果沒有則添加新的鍵，如果存在就直接將該單詞添加到該鍵所對應(yīng)的值數(shù)組里面。

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表中的數(shù)據(jù)，放入res結(jié)果中
    for (auto i: mymap) {
        res.push_back(i.second);
    }

    return res;
}

無重復(fù)字符的最長子串

1. 題目

求給定的字符串中，無重復(fù)字符的最長子串

2. 思路

考慮在一次遍歷的過程中能夠得到想要的結(jié)果，此時需要使用兩個指針，維護(hù)一個滑動窗口，窗口中的字符串即為我們要求的最長子串。這時問題就變成了怎么維護(hù)這個滑動窗口，兩個指針分別在什么時候移動，怎么移動；

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中沒有出現(xiàn)過該字符
            word += str[i];
            if (result < word.length()) {
                result = word.length();
            }
        }
        else {  // 如果在word中出現(xiàn)過
            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;
}