LeetCode之String题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

    public String countAndSay(int n) {
        String init = "1";
        for (int i = 1; i < n; i++) {
            init = countAndSay(init);
        }
        return init;
    }
    String countAndSay(String string) {
        char[] str = string.toCharArray();
        String s = "";
        int p = 1;
        int count = 1;
        char last = str[0];
        for (; p < str.length; p++) {
            if (str[p] == last) {
                count++;
            } else {
                s += "" + count + last;
                count = 1;
                last = str[p];
            }
        }
        s += "" + count + last;
        return s;
    }

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

斐波那契数列和台阶问题的变形，只不过加了一个条件判断。

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        char[] c = s.toCharArray();
        // 对于台阶，需要前两步的值，所以数组最小是3
        int[] step = new int[Math.max(n + 1, 3)];
        step[0] = 1;
        step[1] = 0;
        // 第一个字符不是0，则第一步初始为1
        if (c[0] != '0') {
            step[1] = 1;
        }
        // step[i] = step[i - 1] + step[i - 2];
        // 只不过加step[i - 2]时，需要对c[i - 2]和c[i - 1]判断，组合是否<=26
        for (int i = 2; i <= n; i++) {
            step[i] = 0;
            if (c[i - 1] != '0') {
                step[i] += step[i - 1];
            }
            if (c[i - 2] != '0') {
                if ((c[i - 2] - '0') * 10 + (c[i - 1] - '0') <= 26) {
                    step[i] += step[i - 2];
                }
            }
        }
        return step[n];
    }

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

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

Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null
                || haystack.length() < needle.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        for (int i = 0; i < haystack.length(); i++) {
            if (i + needle.length() > haystack.length()) {
                return -1;
            }
            int m = i;
            for (int j = 0; j < needle.length(); j++) {
                if (needle.charAt(j) == haystack.charAt(m)) {
                    if (j == needle.length() - 1) {
                        return i;
                    }
                    m++;
                } else {
                    break;
                }
            }
        }
        return -1;
    }

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = 0;
        int i = s.length() - 1;
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        while (i >= 0 && s.charAt(i) != ' ') {
            len++;
            i--;
        }
        return len;
    }

 Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input: Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

    static final char[][] CHAR_MAP = { {},// 0
            {},// 1
            { 'a', 'b', 'c' },// 2
            { 'd', 'e', 'f' },// 3
            { 'g', 'h', 'i' },// 4
            { 'j', 'k', 'l' },// 5
            { 'm', 'n', 'o' },// 6
            { 'p', 'q', 'r', 's' },// 7
            { 't', 'u', 'v' },// 8
            { 'w', 'x', 'y', 'z' } // 9
    };
    List<String> result;
    char[] stack;
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<String>();
        }
        result = new ArrayList<String>();
        stack = new char[digits.length()];
        dfs(digits.toCharArray(), 0);
        return result;
    }
    private void dfs(char[] digits, int p) {
        if (p == digits.length) {
            result.add(new String(stack));
        } else {
            int num = digits[p] - '0';
            for (char c : CHAR_MAP[num]) {
                stack[p] = c;
                dfs(digits, p + 1);
            }
        }
    }

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String string = strs[0];
        for (int i = 0; i < string.length(); i++) {
            for (int j = 1; j < strs.length; j++) {
                if (!(i < strs[j].length() && string.charAt(i) == strs[j]
                        .charAt(i))) {
                    return string.substring(0, i);
                }
            }
        }
        return string;
    }

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, and there exists one unique longest palindromic substring.

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int len1 = longest(s, i, i);
            int len2 = longest(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (end - start < len) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int longest(String s, int left, int right) {
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        if (s.length() == 0 || s.length() == 1) {
            return s.length();
        }
        char[] c = s.toCharArray();
        // barrier：0~i中，第一个不重复字符的位置
        int barrier = 0;
        int maxLen = 1;
        for (int i = 1; i < c.length; i++) {
            for (int j = i - 1; j >= barrier; j--) {
                if (c[i] == c[j]) {
                    // 第一个不重复字符的位置为j+1，因为每次j从i-1递减到barrier
                    barrier = j + 1;
                    break;
                }
            }
            maxLen = Math.max(maxLen, i - barrier + 1);
        }
        return maxLen;
    }

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

    List<String> rt = new ArrayList<String>();
    String[] stack = new String[4];
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<String>();
        }
        dfs(s, 0, 0);
        return rt;
    }
    /**
     * 
     * @param s
     * @param p
     *            :指针
     * @param pstack
     *            :stack的下标
     */
    public void dfs(String s, int p, int pstack) {
        if (pstack == 4) {
            // 如果stack长度为4，且s的字符全部用上
            // 则stack[0...3]存了一个结果
            if (p >= s.length()) {
                String ip = String.join(".", stack);
                rt.add(ip);
            }
            return;
        }
        // 获取1~3个字符
        for (int i = 1; i <= 3; i++) {
            // 如果超过字符串长度，返回
            if (p + i > s.length()) {
                return;
            }
            // 若选取的第一个字符是0，则停止选取
            if (i > 1 && s.charAt(p) == '0') {
                continue;
            }
            String number = s.substring(p, p + i);
            // 如果number<=255，递归
            if (Integer.parseInt(number) <= 255) {
                stack[pstack] = number;
                dfs(s, p + i, pstack + 1);
            }
        }
    }

Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

常规的做法是：

1. 将字符串首尾的空格（leading or trailing spaces）去掉
2. 翻转每个单词
3. 翻转整个字符串

例如字符串：“the sky”

翻转前：

the sky

翻转每个单词：

eht yks

翻转整个字符串：

sky the

利用Java的API，解这个题目只需要3行代码。 
参考自：Reverse Words in a String

    public String reverseWords(String s) {
        List<String> words = Arrays.asList(s.trim().split(" +"));
        Collections.reverse(words);
        return String.join(" ", words);
    }

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

    public String simplifyPath(String path) {
        if (path == null) {
            return null;
        }
        String[] names = path.split("/");
        int eat = 0;
        LinkedList<String> stack = new LinkedList<String>();
        for (int i = names.length - 1; i >= 0; i--) {
            String token = names[i];
            // token是".."， 表示上级路径，前一个路径不打印
            // token是"."， 表示当前路径，自身不打印
            // token是"", 表示为两个"/"相连，不做操作
            // eat>0，表示左边不打印
            // 否则，将token入栈
            if (token.equals("..")) {
                eat++;
            } else if (token.equals(".")) {
                // do nothing
            } else if (token.equals("")) {
                // do nothing
            } else {
                if (eat > 0) {
                    eat--;
                } else {
                    stack.push(token);
                }
            }
        }
        StringBuilder s = new StringBuilder();
        s.append("/");
        // 最后一个不加"/"，所以while判断条件是>1
        while (stack.size() > 1) {
            s.append(stack.pop());
            s.append("/");
        }
        // 最后一个不加"/"
        if (!stack.isEmpty()) {
            s.append(stack.pop());
        }
        return s.toString();
    }

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

    public boolean isPalindrome(String s) {
        if (s.length() <= 1) {
            return true;
        }
        char[] chars = s.toLowerCase().toCharArray();
        for (int st = 0, ed = chars.length - 1; st <= ed; st++, ed--) {
            while (st < ed && !isValid(s, st))
                st++;
            while (st < ed && !isValid(s, ed))
                ed--;
            if (chars[st] != chars[ed])
                return false;
        }
        return true;
    }
    boolean isValid(String s, int i) {
        char c = s.charAt(i);
        return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')
                || (c >= 'A' && c <= 'Z');
    }

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

    public boolean isValid(String s) {
        if (s == null || s.length() % 2 == 1) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.keySet().contains(c)) {
                stack.push(c);
            } else if (map.values().contains(c)) {
                if (!stack.empty() && map.get(stack.peek()) == c) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.empty();
    }