(）

最长回文子串

 

最长回文子串

 

// 动态规划public String longestPalindrome(String s) {    int n = s.length();    String res = null;    boolean[][] dp = new boolean[n][n];    for (int i = n - 1; i >= 0; i--) {        for (int j = i; j < n; j++) {            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);            if (dp[i][j] && (res == null || j - i + 1 > res.length())) {                res = s.substring(i, j + 1);            }        }    }    return res;}// 左右扩展public String longestPalindrome(String s) {    if(s==null || s.length()==0){        return null;    }    int longest = 0;    int start = 0;    int len = s.length();    if(len<2){        return s;    }    for(int i=0; i
     
      =0 && n
      
       longest){                longest = n-m+1;                start = m;            }            m--;            n++;        }    }    for(int i=0; i
       
        =0 && n
        
         longest){                longest = n-m+1;                start = m;            }            m--;            n++;        }    }    return s.substring(start, start+longest);}
        
       
      
     

 

 

 有效的括号序列

给定一个字符串所表示的括号序列，包含以下字符：(, ), {, }, [, ],  判定是否是有效的括号序列。

public class Solution {    public boolean isValidParentheses(String s) {        Stack
     
       stack = new Stack
      
       ();        for (Character c : s.toCharArray()) {            if ("({[".contains(String.valueOf(c))) {                stack.push(c);            } else {                if (!stack.isEmpty() && is_valid(stack.peek(), c)) {                    stack.pop();                } else {                    return false;                }            }        }        return stack.isEmpty();    }    private boolean is_valid(char c1, char c2) {        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')                || (c1 == '[' && c2 == ']');    }}
      
     

 

 

 

生成括号

给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。

样例：n = 3, 可生成的组合: "((()))", "(()())", "(())()", "()(())", "()()()"

解答：

public List
     
       generateParenthesis(int n) {    List
      
        list = new ArrayList<>();    if(n==0){        return list;    }    dfs(list, "", n, n);    return list;}private void dfs(List
       
         list, String paren, int left, int right){    if(left==0 && right==0){        list.add(paren);        return;    }    if(left>0){        dfs(list, paren+"(", left-1, right);    }    if(right>0 && left
       
      
     

 

 

 

 解码方法 512

有一个消息包含A-Z通过以下规则编码：

'A' -> 1

'B' -> 2

...

'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式

样例：给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2。

解答：动态规划。dp[n]表示对n个字符有多少中编码方式。最后return结果为dp[s.length()]。

　　分析：对于dp[i]，先判断第i个字符（从1开始数）是否为0。如果不为0，dp[i] = dp[i-1]。再判断第i-1和第i个数组成的数是否在10到26之间，如果是，dp[i] = dp[i]+dp[i-2]。

　　样例：1210924

public int numDecodings(String s) {    if(s==null || s.length()==0){        return 0;    }    int n = s.length();    int[] dp = new int[n+1];    dp[0] = 1;    dp[1] = s.charAt(0)=='0' ? 0:1;    for(int i=2; i<=n; i++){        int first = Integer.valueOf(s.substring(i-1, i));        int second = Integer.valueOf(s.substring(i-2, i));        if(first>=1){            dp[i] = dp[i-1];        }        if(second>=10 && second<=26){            dp[i] += dp[i-2];        }    }    return dp[n];}

 

是否回文串

给定一个字符串，判断其是否为一个回文串。判断的时候只考虑其中的字母和数字。

样例："A man, a plan, a canal: Panama" 是一个回文。

解答：最左和最右两个指针，在每次比较这两个指针的时候都要先判断其是不是字母或数字。

public boolean isPalindrome(String s) {    if(s==null || s.length()==0){        return true;    }        int left = 0;    int right = s.length()-1;     while(left
     
      =0 && !isValid(s.charAt(right))){            right--;        }                if(Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))){            left++;            right--;        }else{            break;        }    }        return right<=left;}private boolean isValid(char c){    return Character.isLetter(c) || Character.isDigit(c);}