Merge branch 'master' of github.com:soulmachine/leetcode

soulmachine · soulmachine · commit f1b35ae41b4d · 2013-12-27T00:41:39.000+08:00
diff --git a/C++/chapSearching.tex b/C++/chapSearching.tex
@@ -179,6 +179,7 @@ \subsubsection{代码}
 class Solution {
 public:
     bool searchMatrix(const vector<vector<int>>& matrix, int target) {
+        if (matrix.empty()) return false;
         const size_t  m = matrix.size();
         const size_t n = matrix.front().size();
 
diff --git a/C++/chapStackAndQueue.tex b/C++/chapStackAndQueue.tex
@@ -104,27 +104,22 @@ \subsubsection{使用栈}
 \subsubsection{Dynamic Programming, One Pass}
 \begin{Code}
 // LeetCode, Longest Valid Parenthese
-// 时间复杂度O(n)，空间复杂度O(1)
-// @author 一只杰森(http://weibo.com/2197839961)
+// 时间复杂度O(n)，空间复杂度O(n)
+// @author 一只杰森(http://weibo.com/wjson)
 class Solution {
 public:
     int longestValidParentheses(string s) {
-        if (s.empty()) return 0;
+        vector<int> f(s.size(), 0);
         int ret = 0;
-        int* d = new int[s.size()];
-        d[s.size() - 1] = 0;
         for (int i = s.size() - 2; i >= 0; --i) {
-            if (s[i] == ')') d[i] = 0;
-            else {
-                int match = i + d[i + 1] + 1;  // case: "((...))"
-                if (match < s.size() && s[match] == ')') {  // found matching ')'
-                    d[i] = match - i + 1;
-                    if (match + 1 < s.size()) d[i] += d[match + 1];  // more valid sequence after j: "((...))(...)"
-                } else {
-                    d[i] = 0;  // no matching ')'
-                }
+            int match = i + f[i + 1] + 1;
+            // case: "((...))"
+            if (s[i] == '(' && match < s.size() && s[match] == ')') {
+                f[i] = f[i + 1] + 2;
+                // if a valid sequence exist afterwards "((...))()"
+                if (match + 1 < s.size()) f[i] += f[match + 1];
             }
-            ret = max(ret, d[i]);
+            ret = max(ret, f[i]);
         }
         return ret;
     }
