Wildcard Matching

来源：Leetcode

原帖：https://oj.leetcode.com/problems/wildcard-matching/

题目：
 Implement wildcard pattern matching with support for '?' and '*'.
 '?' Matches any single character.
 '*' Matches any sequence of characters (including the empty sequence).
 The matching should cover the entire input string (not partial).
 The function prototype should be:
 bool isMatch(const char *s, const char *p)
 Some examples:
 isMatch("aa","a") ? false
 isMatch("aa","aa") ? true
 isMatch("aaa","aa") ? false
 isMatch("aa", "*") ? true
 isMatch("aa", "a*") ? true
 isMatch("ab", "?*") ? true
 isMatch("aab", "c*a*b") ? false

代码：

 class Solution {  
 public:  
   // s does NOT include '?' and '*'. p has '?' and '*'  
   //Version 1: iteration  
   bool isMatch(const char *s, const char *p) {  
     const char *start_s = NULL, *start_p = NULL;  
     while (*s != '\0') {  
       if (*p == '?' || *s == *p) {  
         s++;  
         p++;  
       } else if (*p == '*') {  
         while (*p == '*') p++;  
         if (*p == '\0') return true;  
         start_s = s;  
         start_p = p;  
       } else {  
         if (!start_s) return false;  
         s = ++start_s;  
         p = start_p;  
       }  
     }  
     while (*p == '*') p++;  
     return *s == '\0' && *p == '\0';  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: recursion:   
   // time limit exceed  
   bool isMatch(const char* s, const char* p) {  
     if (*s == '\0') {  
       while(*p && *p == '*') p++;  
       return *p == '\0';  
     }  
     if (*s == *p || *p == '?') {  
       return isMatch(s+1, p+1);  
     } else if (*p == '*') {  
       while (*p == '*') p++;  
       if (*p == '\0') return true;  
       while (*s != '\0') {  
         if (isMatch(s, p)) return true;  
         s++;  
       }  
     }  
     return false;  
   }  
 };  

Regular Expression Matching

来源：Leetcode

原帖：http://oj.leetcode.com/problems/regular-expression-matching/

题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true  zero or more

思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。

代码：

 class Solution {  
 public:  
   bool isMatch(const char *s, const char *p) {  
     if (*p == '\0') return *s == '\0';  
     if (*(p+1) == '*') {  
       if (isMatch(s, p+2)) return true; // match 0  
       while (*s && (*s == *p || *p == '.')) { // match 1,2,...  
         if (isMatch(s+1, p+2)) return true;  
         s++;  
       }  
     } else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s  
         return true;  
     return false;  
   }  
 };  
   
 // dp solution  
 class Solution {  
 public:  
   bool isMatch(const char* s, const char* p) {  
     if (*p == '\0') return *s == '\0';  
     int M = strlen(s), N = strlen(p);  
     vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配  
     dp[0][0] = true;  
     for (int j = 0; j < N; ++j)  
       dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (s[i] == p[j] || p[j] == '.') {  
           dp[i+1][j+1] = dp[i][j];  
         } else if (p[j] == '*') {  
           dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);  
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };  

186 Reverse Words In a String II

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-words-in-a-string-ii/

题目：
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue", return "blue is sky the".
Could you do it in-place without allocating extra space?

代码：

 class Solution {  
 public:  
   // in-place reverse  
   void reverseWords(string &s) {  
     reverse(s.begin(), s.end());  
     int end = 0;  
     for (int i = 0; i < s.size(); ++i) {  
       if (s[i] == ' ') continue;  
       if (end != 0) s[end++] = ' ';  
       int l = i, h = i;  
       while (i != s.size() && s[i] != ' ') {  
         h++; i++;  
       }  
       reverse(s.begin() + l, s.begin() + h);  
       for (int j = l; j < h; ++j) {  
         s[end++] = s[j];  
       }  
     }  
     s.resize(end);    
   }  
 };  

157 Read N Characters Given Read4

来源：Leetcode

原帖：https://leetcode.com/problems/read-n-characters-given-read4/

题目：
The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.
// Forward declaration of the read4 API.
int read4(char *buf);

代码：

 class Solution {  
 public:  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
   int read(char *buf, int n) {  
     char buffer[4];  
     int cnt = 0;  
     while (cnt < n) {  
       int sz = read4(buffer);  
       if (cnt + sz >= n) {  
         memcpy(buf+cnt, buffer, n-cnt);  
         cnt = n;  
       } else {  
         memcpy(buf+cnt, buffer, sz);  
         cnt += sz;  
       }  
       //sz = min(sz, n-cnt);  
       //memcpy(buf + cnt, buffer, sz);  
       //cnt += sz;  
       if (sz < 4) break;  
     }  
     return cnt;  
   }  
 };  

151 Reverse Words In a String I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/reverse-words-in-a-string/

题目：
Given an input string, reverse the string word by word. For example,
Given s = "the sky is blue", return "blue is sky the".
click to show clarification. Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word. Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. How about multiple spaces between two words? Reduce them to a single space in the reversed string.

代码：

 class Solution {  
   void reverseWords(string &s) {  
     stringstream ss(s);  
     vector<string> vs;  
     string word;  
     while (ss >> word) {  
       vs.push_back(word);  
     }  
     reverse(vs.begin(), vs.end());  
     for (size_t i = 0; i < vs.size(); ++i {  
       if (i ! = 0) ss << ' ';  
         ss << vs[i];  
     }  
     s = ss.str();  
   }  
 };  
   
 class Solution {  
 public:  
   void reverseWords(string &s) {  
     string result;  
     int pos = 0;  
     for (int i = 0; i < s.size(); i ++){  
       if (s[i] == ' '){  
         if (i > pos )  
           result = s.substr(pos,i-pos)+ " " + result ;  
         pos = i + 1;  
       }  
       else if (i == s.size()-1)  
         result = s.substr(pos,s.size()-pos)+" "+result;  
     }  
     s = result.substr(0,result.size()-1) ;  
   }  
 };  
   

Permutation Sequence

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutation-sequence/

题目：
The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
 "123"
 "132"
 "213"
 "231"
 "312"
 "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Solution: k = 3 return "231"

代码：

 class Solution {  
 public:  
   // permuation problem, not graph problem  
   string getPermutation(int n, int k) {  
     // index k starting from 0.  
     string num, res;  
     int total = 1;  
     for (int i = 1; i <= n; ++i) { // push back "123"  
       num.push_back(i + '0');  
       total *= i;  
     }  
   
     k--; // index starting from 0  
     while (n) {  
       total /= n;  
       int i = k / total; // i-th group (start from 0)  
       k %= total; // (start from 0) k-th element i-th group  
       res.push_back(num[i]);  
       num.erase(i, 1);  
       n--;  
     }  
     return res;  
   }  
 };  

Longest Common Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
                 = MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]
intialize: f[i][0] = 0
               f[0][j] = 0
answer: f[a.length()][b.length()]

代码：

 int longestCommonSubsequence(string s1, string s2) {  
   int M = s1.size(), N = s2.size();  
   int dp[M + 1][N + 1] = {0};  
   //memset(dp, 0, sizeof(dp));  
   for (int i = 0; i <= M; ++i) {  
     dp[i][0] = 0;  
   }  
     
   for (int j = 0; j <= N; ++j) {  
     dp[0][j] = 0;  
   }  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
       }  
     }  
   }  
   return dp[M][N];  
 }  

Longest Common Substring

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS‘的长度 (一定以第i个和第j个结尾的LCS’)
function: f[i][j]  = f[i-1][j-1] + 1 // a[i] == b[j]
                  = 0 // a[i] != b[j]
intialize: f[i][0] = 0
            f[0][j] = 0
answer: MAX(f[0..a.length()][0..b.length()]

代码：

 int longestCommonSubstring(string s1, string s2) {  
   int M = s1.size(), N = s2.size();   
   vector<vector<int> > dp(M, vector<int>(N,0));  
   for (int i = 0; i <= M; ++i)  
     dp[i][0] = 0;  
   for (int j = 0; j <= N; ++j)  
     dp[0][j] = 0;  
   int maximum = 0;  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = 0;  
       }  
       maximum = max(maximum, dp[i][j]);  
     }  
   }  
   return maximum;  
 }  

Longest Increasing Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
Longest Increasing Subsequence
1 1000 2 3 4
10 11 12 1 2 3 4 13

代码：

 int longestIncreasingSubsequence(const vector<int> &nums) {  
   vector<int> dp(nums.size(), 0);  
   dp[0] = 1;  
   unordered_map<int, vector<int> > map;  
   map[0] = {nums[0]};  
   for (int i = 1; i < nums.size(); ++i) {  
     for (int j = 0; j < i; ++j) {  
       if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {  
         map[i] = move(map[j]);  
         map[i].push_back(nums[i]);  
         dp[i] = max(dp[i], dp[j] + 1);  
       }  
     }  
   }  
   for (auto i : map[nums.size()-1]) cout << i << " ";  
   cout << endl;   
   return dp[nums.size() - 1];  
 }  
   
 int main() {  
   vector<int> nums = {1,2,4,3,2,7,8,9};  
   longestIncreasingSubsequence(nums);  
   return 0;  
 }  

Longest Palindromic Substring

来源：Leetcode

原帖：http://oj.leetcode.com/problems/longest-palindromic-substring/

题目：
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

代码：

 class Solution {  
 public:  
   string longestPalindrome(string s) {  
     int N = s.length();  
     int start = 0, maxlen = 0;  
     for (int center = 0; center < N; center++) {  
       expand(s, center, center, maxlen, start);  
       expand(s, center, center + 1, maxlen, start);  
     }  
     return s.substr(start, maxlen);  
   }  
     
   void expand(const string& s, int left, int right, int& maxlen, int& start){  
     while (left >= 0 && right < s.length() && s[left] == s[right]) {  
       left--;   
       right++;  
     }  
     if (right - left - 1 > maxlen) {  
       maxlen = right - left - 1;  
       start = left + 1;  
     }  
   }  
 };  

Interleaving String

来源：Leetcode

原帖：http://oj.leetcode.com/problems/interleaving-string/

题目：
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution: 1. dp. O(MN) time & space. 'dp[i][j] == true' means that there is at least one way to construct the string s3[0...i+j-1] by interleaving s1[0...j-1] and s2[0...i-1].

代码：

 class Solution {  
 public:  
   //Version 1: dp  
   bool isInterleave(string s1, string s2, string s3) {  
     int M = s1.size(), N = s2.size(), K = s3.size();  
     if (M + N != K) return false;  
     if (s1.empty()) return s2 == s3; // corner case  
     if (s2.empty()) return s1 == s3;  
     vector<vector<bool> > dp(N + 1, vector<bool>(M + 1, false));  
     for (int i = 1; i <= N; ++i)  
       dp[i][0] = s2[i - 1] == s3[i - 1];  
     for (int j = 1; j <= M; ++j)  
       dp[0][j] = s1[j - 1] == s3[j - 1];        
     for (int i = 1; i <= N; ++i) {  
       for (int j = 1; j <= M; ++j) {  
         dp[i][j] = dp[i - 1][j] && s2[i - 1] == s3[i + j - 1] ||  
               dp[i][j - 1] && s1[j - 1] == s3[i + j - 1];          
       }  
     }  
     return dp[N][M];  
   }  
 };  

Palindrome Partitioning II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/palindrome-partitioning-ii/

题目：
Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

代码：

 class Solution {  
 public:  
   int minCut(string s) {  
     int N = s.size();  
     // isP[0]: [0,i] is palindrome  
     bool isP[N]; // [j,i] is palindrome; j = [0, 1, ..., i-1]  
     int dp[N];  
     dp[0] = 0;  
     for (int i = 1; i < N; ++i) { // end point  
       isP[i] = true;  
       dp[i] = dp[i-1] + 1; // dp[i-1] + single word cut  
       for (int j = 0; j < i; ++j) {  
         isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true  -> [j...i] is a palindrome; ascending order  
                           // isP[j+1] == true -> [j+1...i-1] is a palindrome  
         if (isP[j]) {  
           dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]            
         }  
       }  
     }  
     return dp[N-1];  
   }  
 };  
   
 // Time Limit Exceed  
 class Solution {  
 public:  
   //Version 2: sequence dp; easier to understand isP  
   void getIsPalindrome(const string &s, vector<vector<bool> > &isP) {  
     int N = s.size();  
     // isP[i][j] (start i, end j is palindrome)  
     for (int i = 0; i < N; ++i) {  
       isP[i][i] = true;        
     }  
     for (int l = 2; l <= N; ++l) {  
       for (int i = 0; i <= N - l; ++i) {  
         isP[i][i + l - 1] = false;  
         if (l == 2) {  
           isP[i][i + l - 1] = (s[i] == s[i + 1]);  
         } else {  
           isP[i][i + l - 1] = (s[i] == s[i + l - 1] && isP[i + 1][i + l - 2]);  
         }    
       }  
     }  
   }  
   
   int minCut(string s) {  
     int N = s.size();  
     vector<vector<bool>> isP(N, vector<bool>(N, false));  
     getIsPalindrome(s, isP);  
     vector<int> dp(N, 0);  
     dp[0] = 0;  
     for (int i = 1; i < N; ++i) {  
       dp[i] = dp[i - 1] + 1;  
       for (int j = 0; j < i; ++j) {  
         if (j == 0 && isP[j][i]) {  
           dp[i] = 0;   
           break;  
         } else if (isP[j][i]) {  
           dp[i] = min(dp[i], dp[j - 1] + 1);  
         }  
       }  
     }  
     return dp[N - 1];  
   }  
 };  

Palindrome Partitioning I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/palindrome-partitioning/

题目：
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
 [
  ["aa","b"],
  ["a","a","b"]
 ]

代码：

 class Solution {  
 public:  
   bool isPalindrome(const string &s) {  
     int i = 0, j = s.size()-1;  
     while (i < j) {  
       if (s[i] != s[j]) return false;  
       i++; j--;  
     }  
     return true;  
   }  
   
   void partitionHelper(const string &s, int start, vector<string> &path, vector<vector<string> >& res) {  
     if (start == s.size()) {  
       res.push_back(path);  
       return;  
     }  
     string palindrom;  
     for (int i = start; i < s.size(); ++i) {  
       palindrom.push_back(s[i]);  
       if (isPalindrome(palindrom)) {  
         path.push_back(palindrom);  
         partitionHelper(s, i + 1, path, res);  
         path.pop_back();           
       }  
     }  
   }  
   
   vector<vector<string>> partition(string s) {  
     vector<string> path;  
     vector<vector<string> > res;  
     partitionHelper(s, 0, path, res);  
     return res;  
   }  
 };  

Scramble String

来源：Leetcode

原帖：http://oj.leetcode.com/problems/scramble-string/

题目：
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
       great
      /     \
     gr    eat
    / \    /  \
   g   r  e   at
              / \
             a   t
To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
       rgeat
      /     \
     rg    eat
    / \    /  \
   r   g  e   at
              / \
             a   t
We say that "rgeat" is a scrambled string of "great". Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
      rgtae
      /    \
     rg    tae
    / \    /  \
   r   g  ta  e
          / \
         t   a
We say that "rgtae" is a scrambled string of "great". Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Solution: 1. 3-dimensional dp.
              'dp[k][i][j] == true' means string s1(start from i, length k) is a scrambled string of
              string s2(start from j, length k).

代码：

 class Solution {  
 public:  
   bool isScramble(string s1, string s2) {  
     if(s1.size() != s2.size()) return false;  
     int N = s1.size();  
     bool dp[N + 1][N][N];  
     for (int k = 1; k <= N; ++k) { // string length k  
       for (int i = 0; i <= N-k; ++i) { // start i  
         for (int j = 0; j <= N-k; ++j) { // start j   
           dp[k][i][j] = false;  
           if (k == 1)  
             dp[1][i][j] = (s1[i] == s2[j]);    
           for (int p = 1; p < k; ++p) { // 把树分成两子树,如果满足scramble，则分成的两个子树一定是scramble  
             if (dp[p][i][j] && dp[k - p][i + p][j + p]   
              || dp[p][i][j + k - p] && dp[k - p][i + p][j]) {  
               dp[k][i][j] = true;   
               break;              
             }  
           }  
         }  
       }  
     }  
     return dp[N][0][0];  
   }  
 };  

Simplify Path

来源：Leetcode

原帖：http://oj.leetcode.com/problems/simplify-path/

题目：
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
Solution: Add an additional '/' at the end of 'path' for simply detecting the end.
/./ not change the path.

代码：

 class Solution {  
 public:  
   //使用栈来记录字符串结果，当遇到/../时，弹出栈  
   //如果用一个栈来一次存储各级路径的directory名字，然后重组，会简便一些，这也是文件路径简化类题目的常用思路。  
   //为了末尾可以顺序遍历栈重组path，我们不用传统的stack lib，而用vector来实现栈，这样可以方便顺序遍历。  
   string simplifyPath(string path) {  
     string result;  
     path.append("/");  
     vector<string> paths;  
     size_t pos = path.find_first_of("/");  
     size_t last = 0;  
     while (pos != string::npos) {  
       string substr = path.substr(last, pos - last);  
       if (substr == "..") {  
         if (!paths.empty()) {  
           paths.pop_back();  
         }  
       } else if (!substr.empty() && substr != ".") {  
         paths.push_back(substr);  
       }  
       last = pos + 1;  
       pos = path.find_first_of("/", last); // "last" position  
     }  
     if (paths.empty()) return "/";  
     for (auto s : paths) {  
       result += "/" + s;  
     }  
     return result;  
   }  
 };  
   
 class Solution {  
 public:  
   string simplifyPath(string path) {  
     vector<string> dirs;  
     path += '/';  
     string cur;  
     for (auto c : path) {  
       if (c != '/') {  
         cur += c;    
       } else {  
         if (cur == "..") {  
           if (!dirs.empty()) {  
             dirs.pop_back();  
           }  
         } else if(cur != "." && !cur.empty()){// cur != ""很重要.  
           dirs.push_back(cur);  
         }  
         cur.clear();  
       }  
     }  
     if (dirs.empty()) return "/";  
     string res;  
     for (auto dir : dirs) {  
       res += "/" + dir;  
     }  
     return res;  
   }  
 };  

165 Compare Version Numbers

来源：Leetcode

原帖：https://leetcode.com/problems/compare-version-numbers/

题目：
Compare two version numbers version1 and version1. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision. Here is an example of version numbers ordering: 0.1 < 1.1 < 1.2 < 13.37

代码：

 class Solution {  
 public:  
   int compareVersion(const string &v1, const string &v2, int i1, int i2){  
     int n1 = 0, n2 = 0;  
     if(i1 >= v1.size() && i2 >= v2.size()) return 0;  
     int j1 = i1, j2 = i2;   
     while (j1 < v1.size() && v1[j1] != '.') n1 = 10*n1 + v1[j1++]-'0';  
     while (j2 < v2.size() && v2[j2] != '.') n2 = 10*n2 + v2[j2++]-'0';  
     if (n1 > n2) return 1;  
     else if (n1 < n2) return -1;  
     else return compareVersion(v1, v2, ++j1, ++j2);  
   }  
   
   int compareVersion(string version1, string version2) {  
     return compareVersion(version1, version2, 0, 0);  
   }  
 };  

Implement strStr()

来源：Leetcode

原帖：http://oj.leetcode.com/problems/implement-strstr/

题目：
Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

代码：

 class Solution {  
 public:  
   int strStr(char *haystack, char *needle) {  
     if (!haystack || !needle) return -1;  
     char* h_start = haystack;  
     while (1) {  
       char *h = haystack, *n = needle;  
       while (*n && *h && *h == *n) {  
         h++; n++;  
       }  
       if (*n == '\0') return haystack - h_start; // match position  
       if (*h == '\0') return -1;  
       haystack++;  
     }  
   }  
 };  
   
 class Solution {  
   char *strStr(char *haystack, char *needle) {  
     if (!haystack || !needle) return NULL;  
     int lenHaystack = strlen(haystack);  
     int lenNeedle = strlen(needle);  
     int i, j;  
     for (i = 0; i <= lenHaystack - lenNeedle; ++i) {  
       for (j = 0; j < lenNeedle; ++j) {  
         if (haystack[i + j] != needle[j]) break;  
       }  
       if (j == lenNeedle) return haystack + i;  
     }  
     return NULL;  
   }  
 };  

Count and Say

来源：Leetcode

原帖：http://oj.leetcode.com/problems/count-and-say/

题目：
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string.

代码：

 class Solution {  
 public:  
   string countAndSay(int n) {  
     string res = "1";  
     for (int i = 2; i <= n; ++i) { // from 1 to n  
       stringstream ss;  
       int start = 0, N = res.size();  
       while (start < N) {  
         int cur = start + 1;  
         while (cur < N && res[cur] == res[start]) {  
           cur++;            
         }  
         ss << (cur - start) << res[start];  
         start = cur;  
       }  
       ss >> res;  
     }  
     return res;  
   }  
 };  
   
 class Solution {  
 public:  
   string countAndSay(int n) {  
     if(n == 0) return "";  
     string s = "1";  
     for (int i = 1; i < n; i++){  
       s = countAndSay(s);  
     }  
     return s;  
   }  
     
   string countAndSay(string s){  
     string str;  
     for(int i = 0; i < s.size(); i++){  
       int count = 1;  
       while(i + 1 < s.size() && s[i+1] == s[i]){  
         count++;   
         i++;  
       }  
       str += to_string(count);  
       str += s[i];  
     }  
     return str;  
   }  
 };  
   

159 Longest Substring with At Most Two Distinct Characters

来源：Leetcode

原帖：https://oj.leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

题目：
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

代码：

 class Solution {  
   int lengthOfLongestSubstringTwoDistinct(string s) {  
     int res = 0, count = 0;  
     vector<int> need(256, 0);  
     int i = 0, j = 0;  
     while (j < s.size()) {  
       if (need[s[j]] == 0) count++;  
       need[s[j]]++;  
       if (count <= 2) {  
         j++;   
         continue;  
       }  
       res = max(res, j - i);  
       while (i < j && count == 3) {  
         need[s[i]]--;  
         if (need[s[i]] == 0) count--;  
         i++;  
       }  
       j++;  
     }  
     res = max(res, j - i);  
     return res;  
   }  
 }  

Minimum Window Substring

来源：Leetcode

原帖：http://oj.leetcode.com/problems/minimum-window-substring/

题目：
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Solution: Use two pointers: start and end.
               First, move 'end'. After finding all the needed characters, move 'start'.
               Use array as hashtable.

代码：

 class Solution {  
 public:  
   string minWindow(string S, string T) {  
     int N = S.size(), M = T.size();  
     if (N < M) return "";  
     int need[256] = {0}, find[256] = {0};  
     for (int i = 0; i < M; ++i) need[T[i]]++;        
     int count = 0;   
     int resStart = -1, resEnd = N;  
     for (int start = 0, end = 0; end < N; ++end) {  
       if (need[S[end]] == 0) continue;    
       if (++find[S[end]] <= need[S[end]]) count++;  
       if (count != M) continue;       
       // move 'start'  
       for (; start < end; ++start) {  
         if (need[S[start]] == 0) continue;  
         if (find[S[start]] == need[S[start]]) break;  
         find[S[start]]--;  
       }        
       // update min window  
       if (end - start < resEnd - resStart) {  
         resStart = start;  
         resEnd = end;  
       }  
     }  
     return (resStart == -1) ? "" : S.substr(resStart, resEnd - resStart + 1);  
   }  
 };