字符串问题-LeetCode3、5（哈希表储存历史信息）

字符串问题：LeetCode #3 #5

1

编程题

【LeetCode #3】无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路： 首先我们现在看一下最简单的一个字符串的查找，比如"ydyw"，首先左边界left=0,我们开始遍历，每遍历一个位置，如果没有重复的元素，那么max_len=i-left+1，然后对max_len进行更新！如果找到一个重复的元素，比如遍历到i=2，此时y重复，那么我们要更新左边界的索引为上一次该元素索引值+1，这样就保证了此时[left:i]即[1:2]中没有元素重复！

由于我们需要使用上一次遍历的索引值，因此我们使用hashmap来进行存储，类似于昨天两数之和的问题，我们可以使用"边遍历边建立hashmap"的思想！

C++代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, max_len = 0;
        unordered_map<char, int> hashmap;
        for(int i = 0;i < s.size(); i++){  
            if(hashmap.find(s[i]) != hashmap.end()){
                left = max(left, hashmap[s[i]]+1);
                // 如果找到了，左边界更新为上一个遍历该元素索引值+1
            }
            max_len = max(max_len, i-left+1);
            hashmap[s[i]] = i;
        }
        return max_len;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

【LeetCode #5】最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb"

解题思路： 判断一个字符串是不是回文字符串，一个很简单的思路就是从中间向两边依次展开判断对应位置是否相等，但题目是让求最长回文子串，那么我们遍历所有的字符，以每个字符为中心向两边拓展，就ok了，但是存在两种情况：

1. "aba", 这种情况我们可以从中心一直向两边拓展，从而使回文子串
2. "abba", 这种情况我们如果直接使用从中心拓展判断，就会出现错误，因此需要从两个相邻的数出发，同时向两边拓展，而不是仅仅从一个中心位置出发

因此我们在遍历时，对于每个字符，都要考虑上面两种情况！

• PalindromeCore(s, i, i);
• PalindromeCore(s, i, i+1);

注意：Coding时注意i, j的位置，正确计算好最大长度！

C++代码：

class Solution {
private:
    int left = 0, maxlen = 1;
public:
    void PalindromeCore(string s, int i, int j){
        while(i >= 0 && j < s.length() && s[i] == s[j]){
            i--; j++;
        }
        if(maxlen < j-i-1){
            left = i+1;  // 由于上面跳出循环i自减了，j自加了
            maxlen = j-i-1;
        }
    }

    string longestPalindrome(string s) {
        if(s.length() < 2){
            return s;
        }
        for(int i = 0;i < s.length(); i++){
            PalindromeCore(s, i, i);
            PalindromeCore(s, i, i+1);
        }
        return s.substr(left, maxlen); 
        // substr实质从left位置开始数maxlen个字符构成的子串
    }

};