LeetCode--第二部分（4）

LeetCode --5 Longest Palindromic Substring
class Solution {
public:
    int isPalindromic(string s, int size, int len){
        for(int i=0; i+size<=len; i++){
            //check s[i]~s[i+size-1]
            int j = 0;
            while(j<size/2){
                if(s[i+j] != s[i+size-1-j])
                    break;
                j+=1;
            }
            if(j==size/2) return i;
        }
        return -1;
    }
    string longestPalindrome(string s) {
        int len = s.size();
        for(int sublen = len; sublen>0; sublen--){
            int ret = isPalindromic(s, sublen, len);
            if(ret>=0) return s.substr(ret, sublen);
        }
        return s;
    }
};
//other guy‘s solution
class Solution {
public:
    string longestPalindrome(string s)
    {
        int sLen = s.length(), maxLen = 0, maxStart = 0;
        int i = 0, l = 0, r = 0, len = 0;
        while(i<=sLen-maxLen/2)
        {
            l = r = i;
            while(r<sLen-1 && s[r+1]==s[r]) r++;
            i = r+1;
            while(l>0 && r<sLen-1 && s[r+1]==s[l-1]) l--, r++;
            len = r-l+1;
            if(maxLen < len) maxLen = len, maxStart = l;
        }
        return s.substr(maxStart, maxLen);
    }
};

LeetCode--20. Valid Parentheses
class Solution {
　　public:
　　bool isValid(string s) {
　　　　vector<char> OpStr;
　　　　int len = s.length();
　　　　char ee;
　　　　for(int i=0; i<len; i++){
　　　　　　switch (s[i]){
　　　　　　　　case ‘(‘:
　　　　　　　　case ‘[‘:
　　　　　　　　case ‘{‘:
　　　　　　　　　　OpStr.push_back(s[i]);
　　　　　　　　　　break;
　　　　　　　　case ‘)‘:
　　　　　　　　　　if(OpStr.empty()) return false;
　　　　　　　　　　ee = OpStr.back();
　　　　　　　　　　if(ee == ‘(‘)
　　　　　　　　　　　　OpStr.pop_back();
　　　　　　　　　　else
　　　　　　　　　　　　return false;
　　　　　　　　　　break;
　　　　　　　　case ‘]‘:
　　　　　　　　　　if(OpStr.empty()) return false;
　　　　　　　　　　ee = *(OpStr.end()-1);
　　　　　　　　　　if(ee == ‘[‘)
　　　　　　　　　　　　OpStr.pop_back();
　　　　　　　　　　else
　　　　　　　　　　　　return false;
　　　　　　　　　　break;
　　　　　　　　case ‘}‘:
　　　　　　　　　　if(OpStr.empty()) return false;
　　　　　　　　　　ee = *(OpStr.rbegin());
　　　　　　　　　　if(ee == ‘{‘)
　　　　　　　　　　　　OpStr.pop_back();
　　　　　　　　　　else
　　　　　　　　　　　　return false;
　　　　　　　　　　break;
　　　　　　　　default:
　　　　　　　　　　return false;
　　　　　　}
　　　　}
　　　　if(OpStr.empty())
　　　　　　return true;
　　　　else
　　　　　　return false;
　　}
};

===Other Guy‘s Opetimazed solution====
#include <stack>
class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case ‘(‘: 
                case ‘{‘: 
                case ‘[‘: paren.push(c); break;
                case ‘)‘: if (paren.empty() || paren.top()!=‘(‘) return false; else paren.pop(); break;
                case ‘}‘: if (paren.empty() || paren.top()!=‘{‘) return false; else paren.pop(); break;
                case ‘]‘: if (paren.empty() || paren.top()!=‘[‘) return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};
=======
bool isValid(string s) {
    stack<char> st;
    for(char c : s){
        if(c == ‘(‘|| c == ‘{‘ || c == ‘[‘){
            st.push(c);
        }else{
            if(st.empty()) return false;
            if(c == ‘)‘ && st.top() != ‘(‘) return false;
            if(c == ‘}‘ && st.top() != ‘{‘) return false;
            if(c == ‘]‘ && st.top() != ‘[‘) return false;
            st.pop();
        }
    }
    return st.empty();

//LeetCode -- 73. Set Matrix Zeroes
//https://www.cnblogs.com/feliz/p/11059445.html

LeetCode -- 65. Valid Number
1.Skip leading spaces.
2.Skip sign bit.
3.Integer, decimal point and fractional parts (make sure at least one digit exists)
4.Exponential bit. (There may be sign bits again and make sure there is digit following)
5.Skip following spaces.
6.Make sure that‘s the end.

bool isNumber(string s)
 {
     int n = s.size();
     if(n == 0) return false;
      
     int i = 0;
     //Skip leading spaces.
     while(s[i] == ‘ ‘) i++;
      
     //Significand
     if(s[i] == ‘+‘ || s[i] == ‘-‘) i++;
      
     int cnt = 0;
     //Integer part
     while(isdigit(s[i]))
     {
         i++;
         cnt++;
     }
     //Decimal point
     if(s[i] == ‘.‘) i++;
     //Fractional part
     while(isdigit(s[i]))
     {
         i++;
         cnt++;
     }
     if(cnt == 0) return false;  //No number in front or behind ‘.‘
      
     //Exponential
     if(s[i] == ‘e‘)
     {
         i++;
         if(s[i] == ‘+‘ || s[i] == ‘-‘) i++;
         if(!isdigit(s[i])) return false;    //No number follows
         while(isdigit(s[i])) i++;
     }
      
     //Skip following spaces;
     while(s[i] == ‘ ‘) i++;
      
     return s[i] == ‘\0‘;
 }