0%

LeetCode String Algorithm

Posted on Edited on In
Symbols count in article: 29k

世界上最快乐的事，莫过于为理想而奋斗——苏格拉底

LeetCode字符串相关题目，其解决思路和具体代码。

面试题：如何把一个String类型的ip地址保存到一个int类型的整型数组里？注意输入的String可能含有非法字符，比如空格等。

解：传入的String本身已经有分隔符”.”分好了，所以这道题不需要额外做LeetCode93题那样的额外的IP地址复原操作，直接利用位运算保存到int里面即可。

当然，后面面试官可能会加大难度，这时候就要去做LeetCode93题那样的复原工作了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public static int IPV4ToInt(String ipv4_string) {
		// 过滤非法字符
		String ipv4_string0 = ipv4_string.replaceAll("\\s+");

		// 切分获取IP各段
		String[] ipv4_string1 = ipv4_string0.split("\\.");
		int result = 0;
		for(int i = ipv4_string1.length - 1; i >= 0; i--) {
			int sliceTemp = Integer.parseInt(ipv4_string1[i]) << 8 * i;
			result |= sliceTemp;
		}
		return result;
	}
}

125.Valid Palindrome(验证回文串)(Easy)

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

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

Example 1:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

1
2
Input: "race a car"
Output: false

解：双指针法（LeetCode国际站）

需要提前学习，Java的Character包装类中有两个对这道题很有用的方法：

  1. Character.isLetterOrDigit()，判断当前内容是否是全英文或数字。但是这有个坑，如果用了中文，识别不出来(默认提供unicode的支持)，可以用Apache Commons子项目中的lang库，CharUtils的isAsciiAlpha(char)、isAsciiNumeric(char)、isAsciiAlphanumberic(char)等对字符进行字母，大小写字母，数字等的判断。——实际上commons项目是一个大宝库，里面提供了很多对JDK增强的API，lang库就是对java.lang的增强。比如使用反射生成toString的ToStringBuilder，使用反射生成hashCode的HashCodeBuilder等。
  2. Character.toLowerCase()，这个方法可以将大写字符转换为小写字符。

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isPalindrome(String s) {
        // 双指针法
        if(s.length() <= 1) return true;
        char[] c = s.toCharArray();
        // i为头，j为尾(最后一个为长度减1)
        int i = 0, j = c.length-1;
        while(i < j) {
            while(i < j && !Character.isLetterOrDigit(c[i])) //剔除所有非字母或数字的字符
                i++;
            while(i < j && !Character.isLetterOrDigit(c[j]))
                j--;
            if(Character.toLowerCase(c[i++]) != Character.toLowerCase(c[j--])) // 统一转换成小写字母再比较
                return false;
        }
        return true;
    }
}

也可以用for循环来写，这样变量直接定义在循环里面，代码更简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPalindrome(String s) {
        // corner case    
        if(s.length() <= 1) return true;
        char[] c = s.toCharArray();
        for(int i = 0, j = c.length-1; i < j;) {
            if(!Character.isLetterOrDigit(c[i])) i++;
            else if(!Character.isLetterOrDigit(c[j])) j--;
            else if(Character.toLowerCase(c[i++]) != Character.toLowerCase(c[j--])) return false;
        }
        return true;
    }
}

后记：受到这道题的启发，当我们需要去解决输入的一个字符串是否为回文串的时候，我们需要向面试官确认三点：空字符串是否为定义为回文串？输入是否会有空格、分隔符等非法字符？输入为字母的话是否都为大写或者小写字母？(数字不用担心，直接用就行)。

前两点对应Character.isLetterOrDigit()方法，第三点对应Character.toLowerCase()方法

680.Valid Palindrome II(验证回文串 II)(Easy)

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

1
2
Input: "aba"
Output: True

Example 2:

1
2
3
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

解：这道题虽然是125的进化版，但是输入已经约定是都是lowercase的character，所以不需要像上面那样再调用Character.isLetterOrDigit了。

解决这道题也可以用双指针，一头一尾。但是这里主要要考虑可以删除一个字符的情况，可以选择左边指针删除或者右边指针删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length()-1;
        while(left < right) {
            // 左右两边的字符不相等的时候，可以跳过一次左边或者右边的字符
            if(s.charAt(left) != s.charAt(right)) {
                return isPalindrome(s, left+1, right) || isPalindrome(s,left, right-1);
            }
            left++; right--;
        }
        return true;
    }
    
    public boolean isPalindrome(String s, int left, int right) {
        while(left < right ) {
            if(s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
    
}

5.Longest Palindromic Substring(最长回文子串)(Mid)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

解：完整分析参考这篇文章

首先要明确回文子串的定义，单个字符，比如”a”，本身就是回文子串。然后如果多于一个字符了，比如两个字符，那必须是”aa”才能是回文子串，三个的话”aba”是回文子串，以此类推。

这道题是647的扩展，647只要求找到有多少回文子串，而这道题要返回最长的回文子串。

方法一：暴力法，枚举所有长度大于2的子串，一共有O(n^2)个，然后对每一个子串进行验证，需要O(n)，总共的时间复杂度为O(n^3)，太大了。

方法二：优化的暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    
    private int lo, maxLen;
    
    public String longestPalindrome(String s) {
        // 优化后的暴力穷举
        int len = s.length();
        if(len < 2) return s;
        
        for(int i = 0; i < len - 1; i++) {
            extendPalindrome(s, i ,i); // odd length
            extendPalindrome(s, i, i+1); // even length
        }
        // 摘取出来s的最长回文
        return s.substring(lo, lo + maxLen);
    }
    
    public void extendPalindrome(String s, int j, int k) {
        // j是向左扩散，k是向右扩散。只要j和k上面的字符相同，就不断地走
        while(j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--; k++;
        }
        // 走完之后，判断当前遍历到的是不是最长的子串，如果是，就更新max长度，同时记录
        //当前遍历的最左边的位置，也就是起点
        if(maxLen < k - j - 1) {
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}

方法三：动态规划。

动态规划用空间换时间，而且对于这种字符串来说，针对字符串的动态规划一般套路是把字符串放到行和列上，处理这个”二维矩阵”的每个字符串之间的关系。

动态规划最关键的步骤是想出来”状态转移方程”，而事实上，”回文”天然就是具有”状态转移”性质的。

可以知道，一个长度为1的字符本身就是回文串、如果长度为2，那么是回文串的条件必须是

定义的状态：用一个boolean[][]类型的二维数组，dp[i][j]表示子串s[i,j]是否为回文子串，具体说来是从下标为i的字符到下标为j的字符的substring是否为回文子串

因为整个遍历的过程，i始终会小于j(一前一后两个指针)，所以在dp的二维矩阵中实际只填写上半部分即可。

初始化可以用一个循环把对角线上所有值都赋为true，但是实际这一步也可以省略，因为单个字符本身就是回文，而后面dp[i][i]也根本不会被参考的。

状态转移方程：dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]

  1. 看到dp[i+1][j-1]就要考虑边界情况，边界条件是[i+1][j-1]不能构成区间，即长度为2，参考”篮子王”的处理边界的思路，可以处理所有长度为2的字符串，即可，不需要额外考虑判断条件。

考虑输出：只要一得到dp[i][j]==true，就记录子串的长度和起始位置。注意没必要截取它，因为截取字符串也要消耗性能，只要记录此时的回文串的”起始位置(start)”和”回文长度(maxLen)”即可

具体思路：

  1. 在子串左边界j逐渐扩大的过程中，枚举左边界可能出现的位置
  2. 左边界枚举的时候可以从小到大，也可以从大到小

这两种思路代码差别仅在于内层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public String longestPalindrome(String s) {
        // 方法二，DP
        // corner case
        int len = s.length();
        if(len < 2 || s == null) return s;
        
        // 记录最长子串的长度的maxLen和起始位置start
        int maxLen = 1, start = 0;
        
        boolean[][] dp = new boolean[len][len];
        
        // 初始化，对角线都为单个元素,全部为true
        // 但是这个初始化过程可以省略，因为只有一个字符的时候肯定是回文
        // dp[i][i]根本不会被其他状态值所参考
        for(int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        
        // i < len-1 是因为最后要加到i+1，也就是下标为len-1的位置
        // 处理长度为2的边界条件，长度为2时i+1和j-1会越界
        for(int i = 0; i < len - 1; i++) {
            if(s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
                maxLen = 2;
                start = i;
            }
        }
        
        for(int j = 2; j < len; j++) {
            for(int i = 0 ;i < j - 1; i++) { // i < j的话长度为2，之前已经处理过了
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }
                
                // 只要dp[i][j]是true,就证明此时子串s[i,j]是回文串
                // 记录此时回文长度和起始位置,用substring的时候下标从1开始
                if(dp[i][j] == true) {
                int tempLen = j - i + 1;
                    if(tempLen > maxLen) {
                        maxLen = tempLen;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start+maxLen);
    }
}
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2)

方法四：中心扩散法

回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。

由于存在奇数的字符串和偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n+n-1 个中心。（n为n个数，n-1为n个数之间的间隙位置数量）

对于一个有n个元素的字符数组来说，索引为0和len-1的元素不需要扩散，因为扩散不出去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

这个方法好处在于逻辑更清晰，在LeetCode用例测试中最后耗时也更短（虽然时间复杂度分析起来和方法三的动态规划都是O(n^2)）。

还有一个马拉车算法，暂时不讲，面试很难写完。

总而言之，”马拉车算法”虽然很著名，但是对待这种字符串的问题，最常用的还是二维的动态规划。实际上，碰到字符串问题，只要牵扯到动态规划，一般都是把这个字符串复制一份，分别放到行和列上。

对于这道题，需要注意：

  1. 用一个boolean[][]的二维数组来做动态规划
  2. 实际只需要填写上半区域的空
  3. 因为“一个回文去掉两头以后，剩下的部分依然是回文(不讨论边界)”，所以状态转移方程可以知道为：dp[i][j]=(s[i] == s[j]) and dp[i+1][j-1],在矩形坐标上来看就是，只要不在边界上，一个为回文的子串的[i][j]位置一定和其左下角的[i+1][j-1]一致
  4. 注意考虑边界问题，即[i+1][j-1]不能组成区间的情况。我们可以单独处理这个情况。实际上这个边界情况就是目标子串长度为2的情况。我们用一个循环单独处理即可

后记

这确实是一道很经典的有关字符串回文子串处理的题目，经过在LeetCode国际站上的学习，除去中心扩散法，找到了一个很简洁的动态规划版本的代码。我上面提供的代码虽然思路很清晰，但是有些冗长或者啰嗦了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public static String longestPalindrome(String s) {
        int n = s.length();
        String res = null;
        int palindromeStartsAt = 0, maxLen = 0;

        boolean[][] dp = new boolean[n][n];
        // dp[i][j] indicates whether substring s starting at index i and ending at j is palindrome
        
        for(int i = n-1; i >= 0; i--) { // keep increasing the possible palindrome string
            for(int j = i; j < n; j++) { // find the max palindrome within this window of (i,j)
                
                //check if substring between (i,j) is palindrome
                dp[i][j] = (s.charAt(i) == s.charAt(j)) // chars at i and j should match
                           && 
                           ( j-i < 3  // if window is less than or equal to 3, just end chars should match
                             || dp[i+1][j-1]  ); // if window is > 3, substring (i+1, j-1) should be palindrome too
                
                //update max palindrome string
                if(dp[i][j] && (j-i+1 > maxLen)) {
                    palindromeStartsAt = i;
                    maxLen = j-i+1;
                }
            }
        }
        return s.substring(palindromeStartsAt, palindromeStartsAt+maxLen);
    }
}

647.Palindromic Substrings(回文子串)(Mid)

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

解：这道题可以完全参考第五题的思路。只是最后输出要求不同，第五题要记录最长的子串，这道题要统计所有子串的数量而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int countSubstrings(String s) {
        //corner case
        if(s.length() == 0 || s == null) return 0;
        int result = 0, len = s.length();
        boolean[][] dp = new boolean[len][len];
        
        // 初始化对角线
        for(int i = 0; i < len ; i++) {
            dp[i][i] = true;
            result++;
        }
        
        // 处理长度为2的边界条件，长度为2时i+1和j-1会越界
        for(int i = 0; i < len - 1; i++) {
            if(s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
                result++;
            }
        }
        
        for(int j = 2; j < len; j++) {
            for(int i = 0; i < j-1; i++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1];
                    if(dp[i][j] == true) result++;
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return result;
    }
}

同上，给出简化的动态规划的代码来解决这道647题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int result = 0;
        
        if(len < 2) return len;
        
        boolean[][] dp = new boolean[len][len];
        
        for(int i = len - 1; i >= 0; i--) {
            for(int j = i; j < len; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                
                if(dp[i][j]) result++;
            }
        }
        return result;
    }
}

820.Short Encoding of Words(单词的压缩编码)(Mid)

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

1
2
3
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

  1. 1 <= words.length <= 2000.
  2. 1 <= words[i].length <= 7.
  3. Each word has only lowercase letters.

解：根据题意，如果单词Y是另一个单词X的一部分，那么Y就不用考虑了，因为X编码之后里面一定包含Y。反过来说，如果单词Y不在任何别的单词X的后缀中出现，那么Y一定是编码字符串的一部分。

因此，此题的目标就是移除words里的所有单词，使得words里没有一个单词是另一个单词的后缀，最后的结果就是sum(word.length + 1 for word in words)

因为题目条件说到words里面的每一个单词长度都不大于7，所以我们可以枚举所有单词，对于每个后缀，我们都将其从words列表中删除。为了查询的高效，可以用哈希表来存储，这里用HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumLengthEncoding(String[] words) {
        // 初始化set
        Set<String> set = new HashSet<>(Arrays.asList(words));
        for(String word : words) {
            for(int k = 1; k < word.length(); k++) {
                // 若当前word中包含了k，将这个单词移除，因为它可以被包含
                set.remove(word.substring(k));
            }
        }
        int ans = 0;
        for(String word : set) {
            // 加1即为"#"
            ans += word.length() + 1;
        }
        // 最后返回总的长度即可
        return ans;
    }
}

43.Multiply Strings(字符串相乘)(Mid)

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

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:

1
2
Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

解：如果只是普通的数字之间的乘法，那是非常简单的。但是需要注意一个规律：两个数字相乘，得到的结果的位数一定不超过相乘的这两个数的长度之和。

所以我们可以直接开辟一个num1.length()+num2.length()的数组。

接下来求结果，基本思路是一个数一个数之间的相乘。

注意传入的字符的位的位置，低位，比如个位，在下标很大的地方，而高位，比如百位，在下标很小的地方，所以循环可以选择从后面开始。

此外，还要注意保存结果的位置，因为低位保存在右边，也就是int数组下标大的位置，(没错，数字的个位、十位、百位的计位方式刚好和数组的0,1,2,3相反，真的很容易晕掉，晕掉了就怀疑人生了……)。总之最后表现出的结果就是posLow的值反而是比posHigh大1的。

每当两个数之间相乘，就让计算的结果的位数往前错开1，具体内容就是，低位的powLow放到j+i+1的位置，高位posHigh放到i+j的位置。然后要计算与mul的和的情况，mul用于保存每次相乘计算之后的结果。

确定了posLow和posHigh之后，针对mul的操作有三步：mul与result[posLow]的位直接相加得到新的mul结果，然后将低位和高位保存到result里面对应的位置上

如果计算的结果前面有0，则需要干掉这些0然后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String multiply(String num1, String num2) {
        // corner case
        int len1 = num1.length(), len2 = num2.length();
        if(len1 == 0 || len2 == 0) return "0";
        // 存储结果
        int[] result = new int[len1 + len2];
        // 两个for循环嵌套，为了从num1和num2中依次取一位，然后依次做乘法
        for(int i = len1 - 1; i >= 0; i--) {
            for(int j = len2 - 1; j >= 0; j--) {
                // 从num1和num2中依次取一位做乘法
                // 取出来单个char后减去'0'，自动转换成ASCII码的计算，得到int值
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // posLow和posHigh相差1，这两个数表示取出来的数每次相乘之后
                // 要填的result的位置
                int posLow = i+j+1;
                int posHigh = i+j;
                // 两数相乘之后还要加上再之前计算所得到的进位，才是当前计算的最终结果
                mul += result[posLow];
                result[posLow] = mul % 10;
                result[posHigh] += mul / 10;
            }
        }
        // 处理结果，用长度可变的StringBuilder
        StringBuilder sb = new StringBuilder();
        // 忽略所有leading zero，只有当前位不为0而且
        for(int res : result) {
            // 如果sb为空而且此时res为0，那么此时res就是leading 0,要跳过
            if(!(sb.length() == 0 && res == 0)) sb.append(res);
        }
        // 如果最后算结果是0，那么直接返回0，解决了乘数是0的case
        return (sb.length() == 0) ? "0" : sb.toString();
    }
}

时间复杂度：O(len1 * len2)

93.Restore IP Addresses(复原IP地址)(Mid)

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

Example:

1
2
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

解：方法一，暴力解决。但是这个暴力的解法本身也是非常巧妙的，枚举所有可能的情况。因为Input本身就不复杂，所以情况并不会非常非常多。

暴力法是一种面试的时候完全可以考虑使用的方法(如果只考虑把题目解出来……)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new LinkedList<>();
        StringBuilder ip = new StringBuilder();
        
        for(int a = 1; a < 4; a++) {
            for(int b = 1; b < 4; b++) {
                for(int c = 1; c < 4; c++) {
                    for(int d = 1; d < 4; d++) {
                                                /*
                         * 1、保障下面subString不会越界
                         * 2、保障截取的字符串与输入字符串长度相同
                         * //1、2比较好理解，3比较有意思
                         * 3、不能保障截取的字符串转成int后与输入字符串长度相同
                         * 如：字符串010010，a=1，b=1，c=1，d=3，对应字符串0，1，0，010
                         * 转成int后seg1=0，seg2=1，seg3=0，seg4=10
                         */
                        if(a + b + c + d == s.length()) {
                            int n1 = Integer.parseInt(s.substring(0,a));
                            int n2 = Integer.parseInt(s.substring(a,a+b));
                            int n3 = Integer.parseInt(s.substring(a+b,a+b+c));
                            int n4 = Integer.parseInt(s.substring(a+b+c));
                            // 四个段数值满足0~255
                            if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255) {
                                ip.append(n1).append('.')
                                    .append(n2).append('.')
                                    .append(n3).append('.')
                                    .append(n4);
                                // 保障截取的字符串转成int后与输入字符串长度相同
                                // 这个判断用于处理特殊情况，即比如输入为 010010，分割成0,1,0,10
                                if(ip.length() == s.length()+3) result.add(ip.toString());
                                ip.delete(0,ip.length());
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}

方法二，递归回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<String> restoreIpAddresses(String s) {
        LinkedList<String> result = new LinkedList<>();
        if(s == null && s.length() > 12) return result;
        restoreHelper(result, s, "", 0);
        return result;
    }
    
    public void restoreHelper(List<String> result, String s, String current, int field) {
        // field:0, 1, 2, 3, 4 means all done
        // 用field判断当前有几段，即几个field，满了4段即为IP地址的格式
        if(field == 4 && s.length() == 0) result.add(current.substring(1)); // remove the prefixed "."
        else if(field == 4 || s.length() == 0) return ;//not valid combination
        else {
            restoreHelper(result, s.substring(1), current + "." + s.substring(0,1), field + 1);
            if(s.charAt(0) != '0' && s.length() > 1) {
                restoreHelper(result, s.substring(2), current + "." + s.substring(0,2),field + 1);
                if(s.length() > 2 && Integer.valueOf(s.substring(0,3)) <= 255) 
                    restoreHelper(result, s.substring(3),current+"."+s.substring(0,3),field+1);
            }
        }
    }
}

Note:重点看暴力法

415.Add Strings(字符串相加)(Easy)

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

Note:

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

解：这道题内核很类似整数反转的过程，主要是提取出每一位的数字，然后计算，加法的话用carry记录是否有进位(加法进位只可能是0或者1)，然后利用除以10得到十位，求余10得到个位。把字符转换成具体数字的操作也很简单，将char减去’0’即可。

这里每次计算都依次放入结果，用StirngBuilder进行保存。但是每次append()之后都是放在了末尾，最后返回结果的时候要reverse()一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder("");
        int len1 = num1.length(), len2 = num2.length();
        int carry = 0;
        for(int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; i--,j--) {
            int charNum1 = i >= 0 ? num1.charAt(i)-'0' : 0;
            int charNum2 = j >= 0 ? num2.charAt(j)-'0' : 0;
            int sum = charNum1 + charNum2 + carry;
            int val = sum % 10;
            carry = sum / 10;
            result.append(val);
        }
        if(carry != 0) result.append(carry);
        return result.reverse().toString();
    }
}

937.Reorder Data In Log Files(重新排列日志文件)(Easy)

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

  • Each word after the identifier will consist only of lowercase letters, or;
  • Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

1
2
Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

Constraints:

  1. 0 <= logs.length <= 100
  2. 3 <= logs[i].length <= 100
  3. logs[i] is guaranteed to have an identifier, and a word after the identifier.

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public String[] reorderLogFiles(String[] logs) {
        
        Comparator<String> myComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1SpaceIndex = s1.indexOf(' ');
                int s2SpaceIndex = s2.indexOf(' ');
                char s1FirstCharacter = s1.charAt(s1SpaceIndex+1);
                char s2FirstCharacter = s2.charAt(s2SpaceIndex+1);
                
                if (s1FirstCharacter <= '9') {
                    if (s2FirstCharacter <= '9') return 0;
                    else return 1;
                }
                if (s2FirstCharacter <= '9') return -1;
                
                int preCompute = s1.substring(s1SpaceIndex+1).compareTo(s2.substring(s2SpaceIndex+1));
                if (preCompute == 0) return s1.substring(0,s1SpaceIndex).compareTo(s2.substring(0,s2SpaceIndex));
                return preCompute;
            }
        };
        
        Arrays.sort(logs, myComp);
        return logs;
    }
}

3.Longest Substring Without Repeating Characters(无重复字符的最长子串)(Mid)

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

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: 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.

解：解法一：暴力法

找到所有子串，然后每一个子串都一个一个地去判断是否有重复的字符。

要分析这个方法的时间复杂度，首先我们需要弄清楚一些问题，假设字符串长度为n，那么它有多少个非空子串？

答案是 n*(n+1)/2 个。

怎么计算出来的？

  • 长度为1的子串，有n个
  • 长度为2的子串，有n-1个
  • 长度为3的子串，有n-2个

…

  • 长度为k的子串，有n-k+1个
  • 当k=n时，n-k+1=1，即长度为n的子串就是1个

所有情况相加，可以得到：
n+(n-1)+(n-2)+(n-3)+…+2+1 = n(n+1)/2
算上空字符串，一共有：(n(n+1)/2) + 1

在这里可以进行对比，子串和子序列的区别。比如，对于长度为n的字符串，一共有多少子序列？

答案是2^n

怎么计算得到的？

  • 子序列不同于子串

  • 子序列中的元素不需要相互挨着

  • 长度为1的子序列有n个，即：C(1,n)

  • 长度为2的子序列有C(2,n)个

  • 长度为3的子序列有C(3,n)个

…

  • 长度为k的子序列有C(k,n)个
  • 所有子序列的个数(包括空序列)为：C(0,n) + C(1,n) + C(2,n) + C(3,n) + … + C(n,n) = 2^n

这里有关统计字符串的子串和子序列的过程和方法，和结果，务必熟悉和记下来，对于分析各种问题能有帮助。

如果对所有的子串进行判断，从每个子串里寻找最长且没有重复字符的，复杂度为：O(n* (n+1)/2 * n) = O(n^3)

当然，这不是最好的办法。

解法二：线性法

  • 把每次遍历到的字符放入到一个哈希集合中，这样每次判断当前遍历过的内容中是否包含下一个要遍历的字符的时候，用哈希表的contains方法，时间复杂度为O(1),比不放到哈希表中的O(n)的速度能够得到提高。

具体解法：

  • 定义一个哈希集合set
  • 从给定字符串的头开始，每次检查当前字符是否在集合内。如果不在，说明该字符不会造成冲突和重复，将其加入到集合中，并统计当前集合长度，或许为最长子串

如果出现了重复的子串，处理方法是定义两个指针，i为慢指针，j为快指针。

当 j 遇到一个重复出现的字符时，我们从慢指针开始一个一个地将 i 指针指向的字符从集合中删除，然后判断是否可以把新字符加入到集合而不会重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 定义一个哈希集合set,初始化结果max为0
        Set<Character> set = new HashSet<>();
        int max = 0;
        
        // 利用快慢指针i(慢)和j(快)扫描一遍字符串
        for(int i = 0, j = 0; j < s.length(); j++) {
            // 如果快指针指向的字符已经出现在哈希集合中,不断尝试将慢指针指向的字符从哈希集合中删除
            while(set.contains(s.charAt(j))) {
                set.remove(s.charAt(i));
                i++;
            }
            
            // 当快指针的字符终于能加入到哈希集合的时候，更新结果max
            set.add(s.charAt(j));
            max = Math.max(max, set.size());
        }
        // 遍历完毕后，返回结果max
        return max;
    }
}
  • 时间复杂度分析：O(n)。使用了快慢指针策略，字符串最多被遍历两次。快指针会被添加到哈希表集合，慢指针遇到的字符会从哈希集合中删除。哈希集合操作时间为O(1)，因此整个算法复杂度为：n * O(1) + n*O(1) = O(n)
  • 空间复杂度分析：O(n)。由于使用到哈希集合，最坏的情况下，即给定的字符串没有任何重复的字符，我们需要把每个字符都加入集合。

解法三：优化的线性法

基于方法二的线性法。也就是，如果我们在遍历过程中遇到了set已经有的字符的时候，如何不让慢指针一步一步移动，而是直接移动到重复元素的后面呢？这样可以大大减少比较次数。

这样一来我们需要能够记录每个字符出现的下标位置，可以用哈希表记录，因为查找过程时间复杂度也是O(1)

而且此时，我们不能像之前一样去数哈希集合的元素作为max的结果。比如可能出现一种情况，就是当前快指针j遍历到的元素在之前已经出现过了，那么此时不能让i又跳回到前面去呀！所以i的值需要有max计算得到：i = Math.max(i, map.get(s.charAt(j) + 1));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 定义一个哈希表map用来记录上次某字符出现的位置,初始化结果max为0
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        
        // 利用快慢指针i(慢)和j(快)扫描一遍字符串
        for(int i = 0, j = 0; j < s.length(); j++) {
            // 如果发现快指针所对应的字符已经出现过，慢指针就进行跳跃
            if(map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)) + 1);
            }
            
            // 把快指针所对应的字符添加到哈希表中，更新结果max
            map.put(s.charAt(j), j);
            max = Math.max(max, j - i + 1);
        }
        // 遍历完毕后，返回结果max
        return max;
    }
}

8.String to Integer (字符串转换整数 (atoi)(Mid)

Implement atoi which converts a string to an integer.

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.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^(31), 2^(31) − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

1
2
Input: "42"
Output: 42

Example 2:

1
2
3
4
Input: "	-42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

1
2
3
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

1
2
3
4
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

1
2
3
4
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

解：atoi，实际上意思是：ASCII to Integer。

我们可以把题目需求分为两部分，数字字符之前的部分和数字字符之后的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int myAtoi(String str) {
        str = str.trim();//干掉所有首和尾的空格
        if(str.length() == 0)
            return 0;
        
        //1表示正数、-1表示负数
        int sign = 1;
        //idx依次指向每一个Character
        int idx = 0;
        
        char c = str.charAt(0);
        
        if(c == '+') {
            sign = 1;
            idx++;
        } else if(c == '-') {
            sign = -1;
            idx++;
        }
        //int可能存不下，用long存
        long sum = 0;
        for(int i = idx;i < str.length(); i++) {
            if(!Character.isDigit(str.charAt(i))) { //当遍历的str的第i个不为数字时跳出
                //无形中处理了一种异常情况：打头的是字母的时候，直接返回0
                return (int)sum * sign;
            }
            //若当前遍历到的为数字，则累加到sum中
            sum = sum * 10 + str.charAt(i) - '0';
            //处理sum大于Integer.MAX_VALUE这个边界条件
            if(sign == 1 && sum > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            //处理sum小于Integer.MIN_VALUE这个边界条件
            if(sign == -1 && (-1) * sum < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
        }
        return (int) sum * sign;
    }
}

14.Longest Common Prefix(最长公共前缀)(Easy)

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

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

解：利用水平扫描法进行遍历，首先遍历第1、2个元素，找到共同的前缀、然后将找到的共同的前缀再利用起来，往后找，直到前缀prefix为空了为止，直接返回空字符串。

注意这里很巧妙地使用了Java的indexOf()方法，其作用是：查找一个字符串中，第一次出现指定字符的位置。即indexOf(int, ch).注意，这个位置是从0开始计数的。如果没有搜索到，返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String longestCommonPrefix(String[] strs) {
        //特判
        if(strs.length == 0) return "";
        //从strs的第一个元素开始作为前缀遍历
        String prefix = strs[0];
        //从第二个开始比遍历每一个字符串
        for(int i = 1; i < strs.length; i++) {
            //这里很巧妙地利用了indexOf这个函数，起始值必须是0才行，因为前缀从头开始
            //如果不是0，那么可能是-1，即无法匹配，则进入循环
            while(strs[i].indexOf(prefix) != 0) {
                //截取prefix，从最后往前截取，长度每次减1
                prefix = prefix.substring(0, prefix.length() - 1);
                //当截取的长度到了0，代表此时prefix为空字符串，即无法匹配到结果
                if(prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

28.Implement strStr()(实现strStr())(Easy)

Implement strStr().

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

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

解：首先注意最后的Clarification(说明)中的内容，当needle为空的时候，我们应该返回什么？这是一个好问题，我们这里返回的是0,(匹配不到才返回-1)，这个和java中的indexOf()和C语言中的strstr()返回的结果相同。

方法一：暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int strStr(String haystack, String needle) {
        int len1 = haystack.length();
        int len2 = needle.length();
        if(len1 < len2) {
            return -1;
        } else if(len2 == 0) {
            return 0;
        }
        for(int i = 0; i < len1 - len2 + 1; i++) {
            if(haystack.substring(i, i+len2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

时间复杂度：O((m-n)n)，m是主字符串、n是模式字符串

方法二：KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
     public int strStr(String S, String T) {
        if (T == null || T.length() == 0) return 0;
        int[] next = new int[T.length()];
        getNext(T, next);
        int i = 0;
        int j = 0;
        while (i < S.length() && j < T.length()) {
            if (j == -1 || S.charAt(i) == T.charAt(j)) {
                i++;
                j++;
            } else j = next[j];
        }
        if (j == T.length()) return i - j;
        return -1;


    }

    private void getNext(String t, int[] next) {
        next[0] = -1;
        int i = 0;
        int j = -1;
        while (i < t.length() - 1) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
}

151.Reverse Words in a String(反转字符串里的单词)(Mid)

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

Example 1:

1
2
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
3
Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

解：详细题解可以参考这篇文章

这道题主要考察两点：

  1. 能否形成有效的算法
  2. 能否处理边界条件

方法一：利用Java语言库中的trim()、split()、reverse()、join()方法

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ",wordList);
    }
}
  • 时间复杂度：O(N)，其中N为输入字符串的长度
  • 空间复杂度：O(N)，用来存储字符串分割之后的结果

方法二：自己编写反转函数，先将经过trim()之后的字符串中每一个字符都倒着放入一个字符串里，此时整个字符串时翻转的，但是每个单词里面也都是翻转的。所以再需要将每一个单词进行一次翻转，即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') ++left;

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') --right;

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') sb.append(c);
            else if (sb.charAt(sb.length() - 1) != ' ') sb.append(c);

            ++left;
        }
        return sb;
    }

    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') ++end;
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }

    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);

        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);

        // 翻转每个单词
        reverseEachWord(sb);

        return sb.toString();
    }
}
  • 时间复杂度：O(N),N为输入字符串的长度
  • 空间复杂度：Java和Python需要O(N)的空间来存储字符串，而C++只需要O(1)的额外空间来存放若干变量。

方法三：用双端队列，每遍历到一个字符串，就放入到队尾即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') ++left;

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') --right;

        Deque<String> d = new ArrayDeque();
        StringBuilder word = new StringBuilder();
        
        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                // 将单词 push 到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());

        return String.join(" ", d);
    }
}
  • 时间复杂度：O(N)，其中N为输入字符串的长度
  • 空间复杂度：O(N)，双端队列存储单词需要O(N)的空间