[Leetcode][String]字符串相关题目汇总/分析/总

2019-04-03 本文已影响0人奔跑的程序媛A

Reverse
- 344 Reverse String
- 541 Reverse String II
- 557 Reverse Words in a String III
- 345 Reverse Vowels of a String
SubString
Convert
- 13 Roman to Integer
- 12 Integer to Roman
- 273 Integer to English Words
Palindrome
- 125 Valid Palindrome
- 680 Valid Palindrome II
- 131 Palindrome Partitioning
- 132 Palindrome Partitioning II
- 214 Shortest Palindrome
Parentheses
- 20 Valid Parentheses
- 22 Generate Parentheses
- 32 Longest Valid Parentheses
- 241 Different Ways to Add Parentheses
- 301 Remove Invalid Parentheses
Remove
- 316 Remove Duplicate Letters

基本String知识

char[] --> string: new String(c)
string --> char[]: s.toCharArray()
int --> string: Integer.toString(i)
str.split(" ") str.trim()
StringBuilder x = new StringBuilder();
x.append(st + " "); x.toString() x.reverse()

#344 Reverse String

Sol 遍历

    public String reverseString(char[] c) {
        for(int i = 0, j = c.length-1; i<=j;i++, j--){
            char tmp = c[i];
            c[i] = c[j];
            c[j] = tmp;
        }
        return new String(c);
    }

#541 Reverse String II

Easy

Sol
每隔k个字符就翻转k个字符，框架

ublic String reverseStr(String s, int k) {
    cha[] c = s.toCharArray();
    for(int i = 0; i < c.length; i += 2*k){
        if(i+k >= length){
            reverse(c, i, c.length-1);
        }else{
            reverse(c, i, i+k-1);
        }
    }
    return new String(c);
}

翻转

public void reverse(char[] s, int start, int end){
    while(start < end){
        char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
        start++;
        end--;
    }
}

#557 Reverse Words in a String III

Easy

Sol

public String reverseWords(String s) {
        String[] word = s.split(" ");
        StringBuilder res = new StringBuilder();
        for(String si : word){
            res.append(reverse(si) + " ");
        }
        return  res.toString().trim();
}
public String reverse(String s){
    char[] c = s.toCharArray();
    for(int i = 0, j = c.length-1; i < j; i++, j--){
        char tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }
    return new String(c);
}

#345 Reverse Vowels of a String

Sol two pointer

public String reverseVowels(String s) {
        char[] c = s.toCharArray();
        for(int i = 0, j = c.length-1; i < j;){
            boolean i_b = (c[j] == 'a' || c[j] == 'e' || c[j] == 'i' || c[j] == 'o' || c[j] == 'u' || c[j] == 'A' || c[j] == 'E' || c[j] == 'I' || c[j] == 'O' || c[j] == 'U');
            boolean i_a = c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u' || c[i] == 'A' || c[i] == 'E' || c[i] == 'I' || c[i] == 'O' || c[i] == 'U';
            if(i_a && i_b){
                char tmp = c[i];
                c[i] = c[j];
                c[j] = tmp;
                i++;
                j--;
            }
            if(!i_a){
                i++;
            }
            if(!i_b){
                j--;
            }
        }
        return new String(c);
}

【SubString】

#1016 Binary String With Substrings Representing 1 To N

int to binary string / substring check

Sol built in function
int数的二进制表示Integer.toBinaryString(i)
判断一个字符串中是否包含某一子字符串 str.indexOf("china")!=-1

    public boolean queryString(String S, int N) {
        for(int i = 1; i <= N; i++){
            String tmp = Integer.toBinaryString(i);
            if(S.indexOf(tmp)==-1){return false;}
        }
        return true;
    }

#647 Palindromic Substrings

计算回文子字符串的个数

Sol 动态规划|对称性
【对称轴】回文串都有某个对称轴（奇数个字符的串对称轴为最中间的字符。偶数不同，偶数的对称轴可以看做两个）.
【回文串的规律】当在回文串两端各加入两个相同的字符的时候，形成的新字符仍旧是回文串。

    int count = 0;
public int countSubstrings(String s) {
    for(int i = 0; i < s.length(); i++){
        help(s, i, i); //奇数
        help(s, i, i+1); //偶数
    }
    return count;
}
public void help(String s, int start, int end){
    while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
        count++;
        start--;
        end++;
    }
}

#5 Longest Palindromic Substring

Sol 类似647

class Solution {
    int max_length = 0;
    String res = "";
    public String longestPalindrome(String s) {
        for(int i = 0; i < s.length(); i++){
            help(s, i, i);
            help(s, i, i+1);
        }
        return res;
    }
    public void help(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            int length = end - start + 1;
            if(length > max_length){
                max_length = length;
                if(end+1 < s.length()) res = s.substring(start, end+1);
                else res = s.substring(start);
            }
            start--;
            end++;
        }
    }
}

#3 Longest Substring Without Repeating Characters

Sol HashMap
<字符，最后出现的位置>

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> m = new HashMap<>();
        int length = s.length();
        int i = 0, j = 0, res = 0;
        while(i < length && j < length){
            if(m.containsKey(s.charAt(j))){
                i = Math.max(i, m.get(s.charAt(j))+1);
            }
            res = Math.max(res, j - i+1);
            m.put(s.charAt(j), j);
            j++;
        }
        return res;
    }

#115 Distinct Subsequences

Sol DP
dp[i][j]表示s[0...j]包含的subsequence个数（==T[0...i]）
Base：dp[0][j] = 1, dp[i][0] = 0
Others：
if(s[j] == T[i]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = dp[i][j-1];

public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length()+1][s.length()+1];
        for(int i = 0; i <= t.length(); i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= s.length(); j++){
            dp[0][j] = 1;
        }
        for(int i = 1; i <= t.length(); i++){
            for(int j = 1; j <= s.length(); j++){
                if(s.charAt(j-1) == t.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[t.length()][s.length()];
    }

#459 Repeated Substring Pattern

Sol One line

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s+s).substring(1, 2 * s.length() - 1).contains(s);
    }
}

【Convert】

#13 Roman to Integer

Sol map暂存

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> roman = new HashMap<>();
        roman.put('I', 1);
        roman.put('V', 5);
        roman.put('X', 10);
        roman.put('L', 50);
        roman.put('C', 100);
        roman.put('D', 500);
        roman.put('M', 1000);
        if(s.length() == 0) return 0;
        int res = roman.get(s.charAt(0));
        for(int i = 1; i < s.length(); i++){
            if(roman.get(s.charAt(i)) > roman.get(s.charAt(i-1))){
                res = res - 2 * roman.get(s.charAt(i-1)) + roman.get(s.charAt(i));
            }else{
                res += roman.get(s.charAt(i));
            }
        }
        return res;
    }
}

#12 Integer to Roman

Sol 分情况考虑

    public String intToRoman(int num) {
        String res = "";
        if(num >= 1000){
            int a = num/1000;
            while(a!=0){
                res = res + "M";
                num = num - 1000;
                a--;
            }
        }
        if(num >= 900){
            res += "CM";
            num = num - 900;
        }
        if(num >= 500){
            res += "D";
            num = num - 500;
        }
        if(num >= 400){
            res += "CD";
            num = num - 400;
        }
        while(num >= 100){
            res += "C";
            num = num-100;
        }
        if(num >= 90){
            res += "XC";
            num = num - 90;
        }
        if(num >= 50){
            res += "L";
            num = num - 50;
        }
        if(num >= 40){
            res += "XL";
            num = num -40;
        }
        while(num >= 10){
            res += "X";
            num = num-10;
        }
        if(num >=9){
            res += "IX";
            num = num - 9;
        }
        if(num >= 5){
            res += "V";
            num = num-5;
        }
        if(num == 4){
            res += "IV";
            num = num-4;
        }
        while(num > 0){
            res += "I";
            num--;
        }
        return res;
    }

#273 Integer to English Words

Sol

    private final String[] belowTen = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    private final String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] belowHundred = new String[] {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        return helper(num); 
    }
    
    private String helper(int num) {
        String result = new String();
        if (num < 10) result = belowTen[num];
        else if (num < 20) result = belowTwenty[num -10];
        else if (num < 100) result = belowHundred[num/10] + " " + helper(num % 10);
        else if (num < 1000) result = helper(num/100) + " Hundred " +  helper(num % 100);
        else if (num < 1000000) result = helper(num/1000) + " Thousand " +  helper(num % 1000);
        else if (num < 1000000000) result = helper(num/1000000) + " Million " +  helper(num % 1000000);
        else result = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
        return result.trim();
    }

[Palindrome]

#125 Valid Palindrome

Sol
str = str.replaceAll("[^a-zA-Z^0-9]", "");提取字符串中的字母数字

    public boolean isPalindrome(String s) {
        String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        String rev = new StringBuffer(actual).reverse().toString();
        return actual.equals(rev);
    }

#680 Valid Palindrome II

Sol Greedy
收尾依次判断，只允许有一个不同。检测（i++，j）||（i，j--）

public boolean validPalindrome(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        for(int i = 0, j = n-1; i < j; i++, j--){
            if(ch[i] != ch[j]){
                if(i + 1 == j) return true;
                return help(s.substring(i, j)) || help(s.substring(i+1, j+1));
                
            }
        }
        return true;
    }
    public boolean help(String s){
        for(int i = 0, j = s.length()-1; i < j; i++, j--){
            if(s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }

#131 Palindrome Partitioning

Sol DP + DFS
dp[i][j]表示s[i..j]是否是palindrome

    boolean[][] dp;
    List<List<String>> res;
    public List<List<String>> partition(String s) {
        int l = s.length();
        res = new ArrayList<>();
        dp = new boolean[l][l];
        dpCreate(s);
        dfs(0, s, new ArrayList<>());
        return res;
        
    }
    public void dfs(int index, String s, List<String> cur){
        if(index >= s.length()) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int i = index; i < s.length(); i++){
            if(dp[index][i]){
                cur.add(s.substring(index, i+1));
                dfs(i+1, s, cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    public void dpCreate(String s){
        int l = s.length();
        for(int i = 0; i < l; i++){
            for(int j = 0; j < l; j++){
                dp[i][j] = isParlindrome(s, i, j);
            }
        }
    }
    public boolean isParlindrome(String s, int i, int j){
        for(;i<j;i++,j--){
            if(s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }

#132 Palindrome Partitioning II

Sol dp
dp[i][j] 表示s[i...j]是都是palindrome
num[i]最小分割数s[0...i]

class Solution {
    public int minCut(String s) {
        int l = s.length();
        char[] c = s.toCharArray();
        boolean[][] dp = new boolean[l][l];
        int[] num = new int[l];
        for(int j = 0; j < l; j++){
            int min = Integer.MAX_VALUE;
            for(int i = 0; i <= j; i++){
                if(c[i] == c[j] && (i+1>=j || dp[i+1][j-1])){
                    dp[i][j] = true;
                    min = (i == 0 ? 0 : Math.min(min, num[i-1] + 1));
                }
            }
            num[j] = min;
        }
        return num[l-1];
    }
}

#214 Shortest Palindrome

Sol1 Two pointer + Recursion
i从左至右遍历，j右至左遍历
Time O(n^2)：worst case，每次递归，string分为两部分T(n)=T(n−2)+O(n)=
O(n)+O(n−2)+O(n−4)+...+O(1) = O(n^2)
Space O(n)存reverse string

class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        int i = 0;
        for(int j = n-1; j >= 0; j--){
            if(s.charAt(i) == s.charAt(j)) i++;
        }
        if(i == n) return s;
        String reverse = rev(s.substring(i));
        return reverse + shortestPalindrome(s.substring(0, i)) + s.substring(i);
    }
    public String rev(String s){
        char[] cc = s.toCharArray();
        int n = s.length();
        for(int i = 0, j = n-1; i < j; i++, j--){
            char c = cc[i];
            cc[i] = cc[j];
            cc[j] = c;
        }
        return new String(cc);
    }
}

Sol2 KMP
Knuth-Morris-Pratt字符串查找算法，reverse(s) + '#' + s组成新string，找出新字符串前缀后缀相等的最大长度

class Solution {
    public String shortestPalindrome(String s) {
        String reverse = rev(s);
        String s_new = s + "#" + reverse;
        int len = s_new.length();
        int[] table = new int[len];
        for(int i = 1; i < len; i++) {
            int t = table[i-1];
            while(t > 0 && s_new.charAt(i) != s_new.charAt(t))
                t = table[t-1];
            if(s_new.charAt(i) == s_new.charAt(t))
                ++t;
            table[i] = t;
        }
        return reverse.substring(0, s.length()-table[len-1]) + s;
    }
    public String rev(String s){
        char[] cc = s.toCharArray();
        int n = s.length();
        for(int i = 0, j = n-1; i < j; i++, j--){
            char c = cc[i];
            cc[i] = cc[j];
            cc[j] = c;
        }
        return new String(cc);
    }
}

[Parentheses]

#20 Valid Parentheses

Sol Stack

    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for(int i = 0; i < s.length(); i++){
            // char c = s.charAt(i);
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                st.push(s.charAt(i));
            }else{
                if(st.isEmpty()) return false;
                char c = st.pop();
                if(c != map.get(s.charAt(i))) return false;
            }
        }
        return st.isEmpty();
    }

#22 Generate Parentheses

Sol (left) + right

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n==0){
            res.add("");
            return res;
        }
        for(int i = 0; i < n; i++){
            for(String left: generateParenthesis(i)){
                for(String right: generateParenthesis(n-i-1)){
                    res.add("("+left+")" + right);
                }
            }
        }
        return res;
    }

#32 Longest Valid Parentheses

Sol
分别从左从右遍历string，计算left与right的值，一旦相等，更新max。

    public int longestValidParentheses(String s) {
        int left = 0, right = 0;
        int max = 0;
        // int start = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                left++;
            }
            if(c == ')') right++;
            if(left == right) max = Math.max(max, 2 * right);
            else if(right > left){
                right = 0;
                left = 0;
            }
        }
        right = 0;
        left = 0;
        for(int i = s.length()-1; i >= 0 ; i--){
            char c = s.charAt(i);
            if(c == '('){
                left++;
            }
            if(c == ')') right++;
            if(left == right) max = Math.max(max, 2 * right);
            else if(left > right){
                right = 0;
                left = 0;
            }
        }
        return max;
    }

Time complexity : O(n). Two traversals of the string.
Space complexity : O(1). Only two extra variables leftleft and rightright are needed.

#241 Different Ways to Add Parentheses

Sol DP
map<String, list<Integer>>

    Map<String, List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String input) {
        if(map.containsKey(input)) return map.get(input);
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i < input.length(); i++){
            if(!Character.isDigit(input.charAt(i))){
                for(int a: diffWaysToCompute(input.substring(0,i))){
                    for(int b: diffWaysToCompute(input.substring(i+1))){
                        ans.add(input.charAt(i) == '+'?a+b:input.charAt(i) == '-'?a-b:a*b);
                    }
                }
            }
        }
        if(ans.isEmpty()) ans.add(Integer.parseInt(input));
        map.put(input, ans);
        return ans;
    }

#301 Remove Invalid Parentheses

Sol DFS

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        List<String> candidate = new ArrayList();
        Set<String> set = new HashSet<>();
        candidate.add(s);
        while(!candidate.isEmpty()){
            for(String p: candidate){
                if(isValid(p)) res.add(p);
            }
            if(!res.isEmpty()) return res;
            List<String> next = new ArrayList();
            for(String p: candidate){
                for(int i = 0; i < p.length(); i++){
                    if(p.charAt(i)!='(' && p.charAt(i)!=')') continue;
                    String ne = p.substring(0,i)+p.substring(i+1);
                    if(!set.contains(ne)){
                        next.add(ne);
                        set.add(ne);
                    }
                }
            }
            candidate = next;
        }
        return res;
    }
    public boolean isValid(String s){
        char[] c = s.toCharArray();
        int count = 0;
        for(int i = 0; i < c.length; i++){
            if(c[i]=='(') count++;
            if(c[i] == ')') count--;
            if(count < 0) return false;
        }
        return count==0;
    }

[Remove]

#316 Remove Duplicate Letters

Sol StringBuilder
Space O(n)
Time O(n)

class Solution {
    public String removeDuplicateLetters(String s) {
        StringBuilder sb = new StringBuilder();
        int[] count = new int[26];
        boolean[] visited = new boolean[26];
        for(char c: s.toCharArray()){
            count[c-'a']++;
        }
        for(char c: s.toCharArray()){
            count[c-'a']--;
            if(!visited[c-'a']){
                while(sb.length()>0 && c < sb.charAt(sb.length()-1) && count[sb.charAt(sb.length() - 1) - 'a'] > 0){
                    visited[sb.charAt(sb.length() - 1) - 'a'] = false;
                    sb.setLength(sb.length() - 1);
                }
                sb.append(c);
                visited[c-'a'] = true;
                
            }   
        }
        return sb.toString();
    }
}