String

Valid Palindrome

Problem

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test {
    public void add(Byte b) {
        b = b++;
    }
    public static void main(String[] args) {
        Test test = new Test();
        Byte a = 127;
        Byte b = 127;
        test.add(++a);
        System.out.print(a + " ");
        test.add(b);
        System.out.print(b + "");
    }
}

Code

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    Test test = new Test();
    Byte a = 127;
    Byte b = 127;
    test.add(++a);
    System.out.print(a + " ");
    test.add(b);
    System.out.print(b + "");
    }

Implement strStr()

Problem

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Analysis

暴力算法的复杂度是 O(m*n) ，代码如下。更高效的的算法有KMP算法、Boyer-Mooer算法和Rabin-Karp
算法。面试中暴力算法足够了，一定要写得没有BUG。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
public int strStr(final String haystack, final String needle) {
    if (needle.isEmpty()) return 0;
    final int N = haystack.length() - needle.length() + 1;
    for (int i = 0; i < N; i++) {
        int j = i;
        int k = 0;
        while (j < haystack.length() && k < needle.length() && haystack.charAt(j) == needle.charAt(k)) {
            j++;
            k++;
        }
        if (k == needle.length()) return i;
    }
    return -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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// KMP，时间复杂度O(N+M)，空间复杂度O(M)
public class Solution {
public int strStr(final String haystack, final String needle) {
return kmp(haystack, needle);
}
/*
* 计算部分匹配表，即next数组.
*
* @param[in] pattern 模式串
* @param[out] next next数组
* @return 无
*/
private static void compute_prefix(final String pattern, final int[] next) {
int i;
int j = -1;
next[0] = j;
for (i = 1; i < pattern.length(); i++) {
while (j > -1 && pattern.charAt(j + 1) != pattern.charAt(i)) j = next[j];
if (pattern.charAt(i) == pattern.charAt(j + 1)) j++;
next[i] = j;
}
}
/*
* @brief KMP算法.
*
* @param[in] text 文本
* @param[in] pattern 模式串
* @return 成功则返回第一次匹配的位置，失败则返回-1
*/
private static int kmp(final String text, final String pattern) {
int i;
int j = -1;
final int n = text.length();
final int m = pattern.length();
if (n == 0 && m == 0) return 0; /* "","" */
if (m == 0) return 0; /* "a","" */
int[] next = new int[m];
compute_prefix(pattern, next);
for (i = 0; i < n; i++) {
while (j > -1 && pattern.charAt(j + 1) != text.charAt(i)) j = next[j];
if (text.charAt(i) == pattern.charAt(j + 1)) j++;
if (j == m - 1) {
return i-j;
}
}
return -1;
}
}