Dynamic Programming

44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), 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). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ?

32. Longest Valid Parentheses 最长有效括号

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4. Difficulty: Hard 这道题比20. Valid Parentheses 验证括号难一些. 解法1 还是利用栈来求解,并定义start记录合法括号串的起始位置.遍历字符串,如果遇到左括号,则将当前下标压栈,如果遇到右括号,如果当前栈为空,则将下一个位置的下标记为start,如果栈不为空,则将栈顶元素取出.此时如果站为空,则更新结果和i-start+1的最大值,否则更新结果为i-栈顶元素的最大值. class Solution { public: int longestValidParentheses(string s) { int res = 0,start = 0; stack<int> m; for (int i=0;i<s.

10. 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 Difficulty: Hard

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. Difficulty:Medium Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 这道题参考Grandyang,他博客里有全套leetcode讲解. 求最长回文串,回文串就是正着读反着读都一样的字符串.下面的解法是以一个字符为中心向两边扩散并比较 解法1: O(n^2) class Solution { public: public: string longestPalindrome(string s) { int startIdx = 0, left = 0, right = 0, len = 0; for (int i = 0; i < s.