【每日算法Day 23】字符串基础5

基于动态规划和中心扩展寻找最长回文子串，基于双指针搜索的子序列验证，基于栈的括号匹配。

LeetCode 5. 最长回文子串 (opens new window)

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

解题思路

动态规划法：

如果[i,j]是回文串且s[i-1]==s[j+1]，则[i-1,j+1]也是回文串。基本情况是：单个字符是回文串，两个相同的字符是回文串。则可以用1个大小为n*n的数组isPalindrome[i][j]来记录从i到j的子串是否为回文串。首先初始化isPalindrome[i][i]=true，表示单个字符是回文串，再扫描字符串长度为2的子串并判断他们是否为回文串。后面针对长度为L=d+1（d=j-i）的子串如果有isPalindrome[i + 1][i + d - 1] && s.charAt(i) == s.charAt(i + d)则isPalindrome[i][i+d]=true。同时比较当前找到的最长回文串长度并更新下标。

该算法时间复杂度为O(n^2)，空间复杂度为O(n^2)。

public String longestPalindrome(String s) {
    if (s==null||s.length()==0) return "";
    int n = s.length();
    boolean[][] isPalindrome = new boolean[n][n];
    int left=0,right=0,maxLen=0;

    for (int d = 0; d <= n - 1; d++) {
        for (int i = 0; i < n - d; i++) {
            switch (d) {
                //初始化长度为1和2的子串
                //其实把初始化语句写在外面，dp前不作switch判断会略微快一点
                case 0:
                    isPalindrome[i][i]=true;
                    break;
                case 1:
                    if (s.charAt(i) == s.charAt(i + 1)) {
                        isPalindrome[i][i+1]=true;
                        left=i;
                        right=i+1;
                    }
                    break;
                //开始DP
                default:
                    if (isPalindrome[i + 1][i + d - 1] && s.charAt(i) == s.charAt(i + d)) {
                        isPalindrome[i][i + d] = true;
                        if (d > maxLen) {
                            maxLen = d;
                            left = i;
                            right = i + d;
                        }
                    }
            }
        }
    }
    //substring遵守左闭右开原则所以right+1
    return s.substring(left,right+1);
}

中心扩展算法：

在DP算法状态转移方程的基础上，我们可以发现任何一回文串都是由其中心的1个字符或2个字符向两侧扩展而来。那么可以遍历原字符串中1个及2个的子串，尝试向两侧扩展回文串，每次比较最长能扩展多长，并更新最长回文子串两侧的索引。这样就省去了O(n^2)大小的DP数组所占的空间。

public String longestPalindrome(String s){
    if (s==null||s.length()==0) return "";
    int start=0,end=0;
    for (int i = 0; i < s.length(); i++) {
        int len1=expand(s,i,i);
        int len2=expand(s,i,i+1);
        int len=Math.max(len1,len2);
        if (len > end - start) {
            start=i-(int)Math.floor(len/2.0);
            end=i+(int)Math.ceil(len/2.0);
        }
    }
    return s.substring(start,end+1);
}

private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    //此时left+1,right-1才是该回文串的两侧边界
    return right-left-2;
}

LeetCode 392. 判断子序列 (opens new window)

题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。

示例

示例 1:
s = "abc", t = "ahbgdc"
返回 true.

示例 2:
s = "axc", t = "ahbgdc"
返回 false.

解题思路

使用两个指针sPointer和tPointer分别扫描s和t，每在t中找到一个和当前s[sPointer]相同的字符，判断sPointer是否已到末尾，是则返回true，否则将两个指针分别向后移一位。当tPointer到末尾但s没有匹配完则返回false。

public boolean isSubsequence(String s, String t) {
    if (s==null||s.length()==0) return true;
    if (t==null||t.length()==0) return false;

    int sPointer=0,tPointer=0;
    while (true) {
        while (tPointer < t.length() && t.charAt(tPointer) != s.charAt(sPointer)) {
            tPointer++;
        }
        if (tPointer == t.length()) {
            return false;
        } else if (sPointer==s.length()-1){
            return true;
        }
        sPointer++;
        tPointer++;
    }
}

或者调用API在t中逐个查找s中的字符，每个字符都找到了则返回true，过程中出现找不到的字符则返回false。

public boolean isSubsequence2(String s, String t) {
    if (s==null||s.length()==0) return true;
    if (t==null||t.length()==0) return false;

    int index = 0, loc;
    for (int i = 0; i < s.length(); i++) {
        loc = t.indexOf(s.charAt(i), index);
        if (loc < 0) return false;
        index = loc + 1;
    }
    return true;
}

LeetCode 20. 有效的括号 (opens new window)

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

解题思路

使用栈结构来解决括号对匹配的问题，官方解法用一个map存储左右括号的映射关系，遇到左括号就push，遇到右括号就比较pop出的元素是否对应。也可以不用map，遇到左括号push对应的右括号就可以了。遍历完字符串且没有返回false的话，如果栈为空则说明所有括号都匹配完毕，返回true。

public boolean isValid(String s) {
    if (s==null||s.length()==0) return true;
    Deque<Character> stack=new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)) {
            case '(':
                stack.push(')');
                break;
            case '{':
                stack.push('}');
                break;
            case '[':
                stack.push(']');
                break;
            default:
                if (stack.isEmpty()||stack.pop()!=s.charAt(i))
                    return false;
        }
    }
    return stack.isEmpty();
}