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]为‘*’：又能够分成两种状况
- p[j]在s呈现0次，这种状况间接跳过p[j]和p[j+1]即可
- 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 无效的括号
题目形容
给定一个只蕴含三种字符的字符串：（ ，） 和 *，写一个函数来测验这个字符串是否为无效字符串。无效字符串具备如下规定：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
- * 能够被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
- 一个空字符串也被视为无效字符串。
该题的简化版（leetcode.20）是没有*的，因而只须要简略地用一个栈判断即可。如果只有(和），那能够连栈都不必。
但这题有*，因而必定无奈用一个栈解决问题。
双栈法
此题的解法仅实用于只有'('和')'的状况。因为只有一种括号类型，因而对于号匹配没有那么严苛的要求——即不要求在判断中肯定要匹配相邻的）或（。
比方：s = (()。咱们在判断时并不一定要要求和第二个(匹配、)和第一个(匹配，因为以后串中，和)理论是等价的，所以咱们在判断时能够先不决定是否要匹配，而能够先把能匹配)的(全副匹配完。对于残余的(和，只须要满足(的数量不比多，且对于每一个(，都有比它地位靠后的*绝对应。
因而，有了双栈解法，思路如下：
- 遇见'('将index入左栈
- 遇见'*'将index入右栈
- 遇见')'出左栈——这一步即为了先将所有的)匹配掉；如果左栈为空，出右栈——曾经没有'('，天然用来替，且这些必定都在以后')'的右边；如果右栈也空，则无奈匹配，返回false
- 遍历完结后，先判断左栈是否比右栈多，如果是，则表明没有足够的*来匹配残余的(了，不满足条件，返回false
- 如果左栈不多于右栈，那剩下的步骤只需顺次判断，对于左栈的每一个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; }};