LeetCode String 题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

3 Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目描述

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, end = 0, ans = 0;
        Set<Character> set = new HashSet<>();
        while (end < s.length()) {
            if (!set.contains(s.charAt(end))) {
                set.add(s.charAt(end++));
                ans = Math.max(ans, set.size());
            } else {
                set.remove(s.charAt(start++));
            }
        }
        return ans;
    }
}

5 Longest Palindromic Substring

https://leetcode.com/problems/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.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

代码

class Solution {
    public String longestPalindrome(String s) {
        int pos = 0, ans = 0, p0 = 0, p1 = 0;
        while (pos < s.length()) {
            for (int i = 0; i <= 1; i++) {
                int start = pos, end = pos + i;
                while (start >= 0 && end < s.length()) {
                    if (s.charAt(start) == s.charAt(end)) {
                        start--;
                        end++;
                    } else {
                        break;
                    }
                }
                if (ans < end - start - 1) {
                    ans = end - start - 1;
                    p0 = start;
                    p1 = end;
                }
            }
            pos++;
        }
        return s.substring(p0 + 1, p1);
    }
}

8 String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/

题目描述

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes:
It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

代码

class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] c = str.trim().toCharArray();
        int i = 0, flag = 1, ans = 0;
        if (c[i] == '+') {
            i++;
        } else if (c[i] == '-') {
            flag = -1;
            i++;
        }
        for (; i < c.length; i++) {
            if (c[i] > '9' || c[i] < '0') {
                break;
            }
            // 防止溢出
            if (ans > Integer.MAX_VALUE / 10
                    || (ans == Integer.MAX_VALUE / 10 && (c[i] - '0') > Integer.MAX_VALUE % 10)) {
                return (flag == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            ans = ans * 10 + c[i] - '0';
        }
        return ans * flag;
    }
}

17 Letter Combinations of a Phone Number

https://leetcode.com/problems/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.

代码

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        List<String> list = Arrays.asList("", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz");
        robot(0, ans, list, "", digits);
        return ans;
    }
    private void robot(int start, List<String> ans, List<String> list, String tmp, String digits) {
        if (tmp.length() == digits.length()) {
            ans.add(tmp);
            return;
        }
        int num = digits.charAt(start) - '0';
        if (num > 1) {
            for (Character c : list.get(num - 1).toCharArray()) {
                robot(start + 1, ans, list, tmp + c, digits);
            }
        }
    }
}

20 Valid Parentheses

https://leetcode.com/problems/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.

代码

class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        for (Character c : s.toCharArray()) {
            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();
    }
}

22 Generate Parentheses

https://leetcode.com/problems/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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        robot(0, 0, n, "", ans);
        return ans;
    }
    private void robot(int left, int right, int n, String tmp, List<String> ans) {
        if (tmp.length() == n * 2) {
            ans.add(tmp);
            return;
        }
        if (left < n) {
            robot(left + 1, right, n, tmp + "(", ans);
        }
        if (right < left) {
            robot(left, right + 1, n, tmp + ")", ans);
        }
    }
}

43 Multiply Strings

https://leetcode.com/problems/multiply-strings/

题目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

代码

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];
                pos[p1] += sum / 10;
                pos[p2] = (sum) % 10;
            }
        }  
        StringBuilder sb = new StringBuilder();
        for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

49 Group Anagrams

https://leetcode.com/problems/group-anagrams/

题目描述

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // sort by letter
            char[] array = s.toCharArray();
            Arrays.sort(array);
            String sortString = String.valueOf(array);
            if (map.containsKey(sortString)) {
                map.get(sortString).add(s);
            } else {
                List<String> list = new ArrayList<>();
                list.add(s);
                map.put(sortString, list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

76 Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

题目描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

代码

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() < t.length() || s.length() == 0) {
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        int left = 0;
        int minLeft = 0;
        int minLen = Integer.MAX_VALUE;
        int count = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) >= 0) {
                    count++;
                }
                while (count == t.length()) {
                    if (right - left + 1 < minLen) {
                        minLeft = left;
                        minLen = right - left + 1;
                    }
                    if (map.containsKey(s.charAt(left))) {
                        map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                        if (map.get(s.charAt(left)) > 0) {
                            count--;
                        }
                    }
                    left++;
                }
            }
        }
        if (minLen > s.length()) {
            return "";
        }
        return s.substring(minLeft, minLeft + minLen);
    }
}

93 Restore IP Addresses

https://leetcode.com/problems/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)

代码

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        robot(0, 0, "", ans, s);
        return ans;
    }
    private void robot(int pos, int dot, String tmp, List<String> ans, String s) {
        if (pos >= s.length()) {
            return;
        }
                if (dot == 3) {
            // 防止都是0的情况，出现0.0.0.0000
            if (isValid(s.substring(pos)) && s.length() - pos <= 3) {
                ans.add(tmp + s.substring(pos));
                return;
            } else {
                return;
            }
        }
        for (int i = 1; i <= 3; i++) {
            if (pos + i <= s.length() && isValid(s.substring(pos, pos + i))) {
                robot(pos + i, dot + 1, tmp + s.substring(pos, pos + i) + ".", ans, s);
            }
        }
    }
    private boolean isValid(String string) {
        if (string.length() > 3) {
            return false;
        }
        int v = Integer.valueOf(string);
        if (string.charAt(0) == '0' && string.length() > 1) {
            return false;
        }
        return v >= 0 && v <= 255;
    }
}

165 Compare Version Numbers

https://leetcode.com/problems/compare-version-numbers/

题目描述

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37

Credits:Special thanks to @ts for adding this problem and creating all test cases.

代码

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int m = Math.max(v1.length, v2.length);
        v1 = Arrays.copyOf(v1, m);
        v2 = Arrays.copyOf(v2, m);
        for (int i = 0; i < m; i++) {
            int n1 = 0;
            int n2 = 0;
            if (v1[i] != null) {
                n1 = Integer.valueOf(v1[i]);
            }
            if (v2[i] != null) {
                n2 = Integer.valueOf(v2[i]);
            }
            if (n1 < n2) {
                return -1;
            } else if (n1 > n2) {
                return 1;
            }
        }
        return 0;
    }
}

227 Basic Calculator II

https://leetcode.com/problems/basic-calculator-ii/

题目描述

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Credits:Special thanks to @ts for adding this problem and creating all test cases.

代码

class Solution {
    public int calculate(String s) {
        int ans = 0;
        if (s == null || s.length() == 0) {
            return ans;
        }
        Deque<Integer> deque = new LinkedList<>();
        char operator = '+'; // 记录上一个操作符
        int tmp = 0;
        for (int i = 0; i < s.length() || tmp > 0; i++) {
            char c = i < s.length() ? s.charAt(i) : '+';
            if (c == ' ') {
                continue;
            }
            if (c >= '0' && c <= '9') {
                tmp = tmp * 10 + c - '0';
            } else {
                switch (operator) {
                case '+':
                    deque.add(tmp);
                    break;
                case '-':
                    deque.add(-tmp);
                    break;
                case '*':
                    deque.add(deque.pollLast() * tmp);
                    break;
                case '/':
                    deque.add(deque.pollLast() / tmp);
                    break;
                }
                tmp = 0;
                operator = c;
            }
        }
        for (int v : deque) {
            ans += v;
        }
        return ans;
    }
}