leetcode 3. 无反复最长字串

题目形容

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

思路

用 mp 记录字符上次呈现的地位，用 last 记录以后起始地位，遇到反复的字符计算 ans，并更新 last。
留神：这里因为有 last 限定了字符串的起始地位，因而每次判断时如果 mp[s[i]]在 last 之前，就不必更新。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {vector<int> mp(129, -1);
        int len = s.length(), ans = 0, last = 0, i = 0;
        for(int i=0; i<len; ++i) {if(mp[s[i]] != -1 && mp[s[i]] >= last) {ans = max(ans, i-last);
                last = mp[s[i]] + 1;
            }
            mp[s[i]] = i;
        }
        ans = max(ans, len-last);
        return ans;
    }
};

leetcode 10. 正则表达式匹配

题目形容

给你一个字符串 s 和一个字符法则 p，请你来实现一个反对 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个后面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是局部字符串。

递归思路

边界状况：s 空 p 空，返回 true；s 不空 p 空，返回 false；

p[j+1]为‘*’：又能够分成两种状况

1. p[j]在 s 呈现 0 次，这种状况间接跳过 p[j]和 p[j+1]即可
2. p[j]在 s 中呈现 n 次，且 n 未知。因为 n 未知，则能够用递归的形式判断 p[j]与 s[i+1]的关系。（当然，持续进行递归的前提是 p[j]==s[i]，否则它们一个字符也匹配不上，只能看是不是状况 1）

p[j+1]不为 ’*’：这个时候只须要判断 p[j]是否等于是 s[i]，如果是，递归 p[j+1]和 s[i+1]

class Solution {
public:
    bool isMatch(string s, string p) {return myisMatch(s.c_str(), p.c_str());
    }
    bool myisMatch(const char* s,const char* p) {if(*p == '\0') return *s == '\0';
        bool flag = *s && (*s == *p || *p == '.');
        if(*(p+1) == '*') {return myisMatch(s, p+2) || (flag && myisMatch(++s, p));
        }
        return flag && myisMatch(++s, ++p);
    }
};

动静布局思路

事实上动规思路和递归一模一样，都是上述三种状况，只不过动规存储了两头后果。
这题比拟容易了解的形式是从后往前递归，只须要设置好 dplen1=true 即可。

class Solution {
public:
    bool isMatch(string s, string p) {int len1 = s.length(), len2 = p.length();
        vector<vector<bool> > dp(len1+1, vector<bool>(len2+1, false));
        dp[len1][len2] = true;
        for(int i=len1; i>=0; --i) {for(int j=len2-1; j>=0; --j) {bool flag = i < len1 && (s[i] == p[j] || p[j] == '.');
                if(j < len2 -1 && p[j+1] == '*') {dp[i][j] = dp[i][j+2] || (flag && dp[i+1][j]);
                }
                else {dp[i][j] = (flag && dp[i+1][j+1]);
                }
            }
        }
        return dp[0][0];
    }
};

leetcode.678 无效的括号

题目形容

给定一个只蕴含三种字符的字符串：（，）和 *，写一个函数来测验这个字符串是否为无效字符串。无效字符串具备如下规定：

1. 任何左括号 (必须有相应的右括号)。
2. 任何右括号 ) 必须有相应的左括号 (。
3. 左括号 (必须在对应的右括号之前)。
4. * 能够被视为单个右括号 )，或单个左括号 (，或一个空字符串。
5. 一个空字符串也被视为无效字符串。

该题的简化版（leetcode.20）是没有 * 的，因而只须要简略地用一个栈判断即可。如果只有 (和），那能够连栈都不必。
但这题有 *，因而必定无奈用一个栈解决问题。

双栈法

此题的解法仅实用于只有 '(‘ 和 ’)’ 的状况。因为只有一种括号类型，因而对于 号匹配没有那么严苛的要求——即不要求在判断中 肯定要匹配相邻的）或（。
比方：s = (()。咱们在判断时并不一定要要求 和第二个 (匹配、) 和第一个 (匹配，因为以后串中， 和)理论是等价的，所以咱们在判断时能够先不决定 是否要匹配，而能够先把能匹配)的 (全副匹配完。对于残余的(和，只须要满足(的数量不比 多，且对于每一个 (，都有比它地位靠后的 * 绝对应。
因而，有了双栈解法，思路如下：

1. 遇见 '(‘ 将 index 入左栈
2. 遇见 ’*’ 将 index 入右栈
3. 遇见 ’)’ 出左栈——这一步即为了先将所有的)匹配掉；如果左栈为空，出右栈——曾经没有 '(‘，天然用 来替，且这些 必定都在以后 ’)’ 的右边；如果右栈也空，则无奈匹配，返回 false
4. 遍历完结后，先判断左栈是否比右栈多，如果是，则表明没有足够的 * 来匹配残余的(了，不满足条件，返回 false
5. 如果左栈不多于右栈，那剩下的步骤只需顺次判断，对于左栈的每一个 index，是否有右栈的更大的 index 来匹配它（这时候 ’*’ 代表 ’)’，天然下标必须比 '(‘ 大）

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> st1, st2;
        int len = s.length();
        for(int i = 0; i < len; ++i) {if(s[i] == '(') {st1.push(i);
            }
            else if(s[i] == '*') {st2.push(i);
            }
            else {if(!st1.empty()) {st1.pop();
                }
                else if(!st2.empty()) {st2.pop();
                }
                else return false;
            }
        }
        if(st1.size() > st2.size()) return false;
        while(!st1.empty() && !st2.empty()) {if(st1.top() < st2.top()) {st1.pop();
                st2.pop();}
            else return false;
        }
        return st1.empty();}
};

贪婪法

贪婪法只容许 '(‘ 残余，且只关怀了'(‘ 的最多和起码残余个数。最多残余意味着将所有 * 都看成是 '(‘，起码残余意味着将所有 ’*’ 看成是 ’)’。
在这个办法中，用 low 标示起码残余，用 high 标识最多残余；而为了解决问题，咱们对 low 和 high 的意义做进一步改变——对于起码残余的状况，因为可能呈现 (太少，因而如果此时还将 * 当成)，必然是不非法的，即此时 low 会小于 0，对于这些 low 小于 0 的状况，咱们并不关怀——因为咱们对 low 的做法是将所有 * 都看成(，但咱们也能够将 * 看成空字符啊，既然 low<0 曾经不非法了，那咱们不用再思考，间接将 * 疏忽一次就能够了。
这里可能会有些不了解，* 不是也能够当成)来解决吗？确实，但这不是 low 关怀的，而是 high 关怀的，low 只关怀最差状况，用方才的形式（疏忽 low<0）剪枝后，low 变相地只是在观测是否存在 * 过多的状况而已。也就是，在字符串遍历完结之后，如果 low 还大于 0，那阐明起码残余的状况下，仍无奈匹配所有的'(‘，那匹配失败。

而对于 high 来说，它每次都将 ’*’ 当作 '(‘，因而在遍历完结后，它是很有可能会大于 0 的。但这并不影响后果，因为当 high 大于 0 时，象征这很可能有过多的 * 被当成'(‘，只有 low==0，即当咱们将所有 * 都当空串时，没有 '(‘ 结余，那串就是非法的。因而，对于 high，咱们在完结时并不关怀它的大小。但在遍历过程中，须要用 high 来防止出现)过多的状况（这是动静的，即达到串的某一个地位，届时的状态可能会呈现 ’)’ 过多）。因为当 high<0 时，阐明即使咱们将 ’*’ 都看作'(‘，以后也没有多余的 '(‘ 来匹配 ’)’ 了。

代码逻辑：
遇 '(‘：low++; high++;
遇 ’)’：若 low>0 则 low–; high–;
遇 ’*’：若 low>0 则 low–; high++;
中途若 high<0 返回 false；完结后若 low>0 返回 false，low== 0 返回 true

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        int len = s.length();
        for(int i=0; i<len; ++i) {if(s[i] == '(') {
                ++low;
                ++high;
            }
            else if(s[i] == ')') {if(low > 0) --low;
                --high;
            }
            else if(s[i] == '*') {if(low > 0) --low;
                ++high;
            }
            if(high < 0) return false;
        }
        return low == 0;
    }
};