0%

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 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

img

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
public class Solution {

public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}

boolean[][] dp = new boolean[len][len];

// 初始化
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}

int maxLen = 1;
int start = 0;

for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {

if (s.charAt(i) == s.charAt(j)) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}

// 只要 dp[i][j] == true 成立,就表示子串 s[i, j] 是回文,此时记录回文长度和起始位置
if (dp[i][j]) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}

Reference
https://leetcode-cn.com/problems/longest-palindromic-substring

Longest Substring Without Repeating Characters

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

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

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.

Solution 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
private static int lengthOfLongestSubstring(String s) {
Set<Character> substring = new HashSet<>();
int res = 0;

if (s == null) {
return res;
}

for (int i = 0; i < s.length(); i++) {
int temp = 0;
int j = i;
while (j < s.length()) {
if (!substring.contains(s.charAt(j))) {
substring.add(s.charAt(j++));
temp++;
} else {
substring.clear();
break;
}
}
res = Math.max(temp, res);
}

return res;

/**
执行用时 :127 ms, 在所有 Java 提交中击败了10.50%的用户
内存消耗 :42.3 MB, 在所有 Java 提交中击败了5.02%的用户
*/
}

Using too much time, so I read the leetcode document.
Here is a SlideWindow method.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static int plus(String s) {
int res = 0;
Set<Character> set = new HashSet<>();
int i = 0, j = i;

while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
res = Math.max(res, set.size());
} else {
set.remove(s.charAt(i++));
}
}

return res;

/**
执行用时 :10 ms, 在所有 Java 提交中击败了64.95%的用户
内存消耗 :41.6 MB, 在所有 Java 提交中击败了5.02%的用户
*/

We can adjust the SlideWindow by increase i - head pointer and j - rear pointer.
This can sharply optimize the complexity of time.

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

Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: “()”
Output: true

Example 2:

Input: “()[]{}”
Output: true

Example 3:

Input: “(]”
Output: false

Example 4:

Input: “([)]”
Output: false

Example 5:

Input: “{[]}”
Output: true

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
class Solution {
public boolean isValid(String s) {
char[] charArray = s.toCharArray();
Stack<Integer> stack = new Stack<>();
if (s == null || s.length() == 0) {
return true;
}

for (int i = 0; i < charArray.length; i++) {
if (trans(charArray[i]) > 0) {
stack.push(trans(charArray[i]));
} else if (trans(charArray[i]) < 0 ) {
if (!stack.isEmpty() && stack.pop() + trans(charArray[i]) == 0) {
continue;
} else {
return false;
}
} else {
return false;
}
}

if (stack.size() == 0) {
return true;
} else {
return false;
}
}

private int trans(char c) {
switch (c) {
case '(': return 1;
case ')': return -1;
case '[': return 2;
case ']': return -2;
case '{': return 3;
case '}': return -3;
default: return 0;
}
}

/**
执行用时 :2 ms, 在所有 Java 提交中击败了91.77%的用户
内存消耗 :37.2 MB, 在所有 Java 提交中击败了5.05%的用户
*/
}

Source code is easy to see.

Reference
https://leetcode-cn.com/problems/valid-parentheses

Longest Common Prefix

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:

Input: [“flower”,”flow”,”flight”]
Output: “fl”

Example 2:

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.

Unsolved

1
2
3
4
5
6
Input:
["aa","a"]
Output:
"aa"
Answer:
"a"
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 static String longestCommonPrefix(String[] strs) {
if (strs == null)
return "";

String res = strs[0];
char[] resChar = res.toCharArray();

for (int i = 0; i < strs.length; i++) {
char[] tempChar = strs[i].toCharArray();
for (int j = 0; j < tempChar.length & j < resChar.length; j++) {
if (resChar[j] != tempChar[j]) {
res = strs[i].substring(0, j);
resChar = res.toCharArray();
break;
}
}
}

return res;
}
}

LeetCode Solution

1
2
3
4
5
6
7
8
9
10
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}

Nice idea to use substring to find out what index is it. If strs doesn’t have a substring the index can not be 0. All we need to do is cut the prefix‘s length.

Reference
https://leetcode-cn.com/problems/longest-common-prefix

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: “III”
Output: 3

Example 2:

Input: “IV”
Output: 4

Example 3:

Input: “IX”
Output: 9

Example 4:

Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

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
class Solution {
public int romanToInt(String s) {
char[] array = s.toCharArray();
int sum = 0;

for (int i = 0; i < array.length - 1; i++) {
if (trans(array[i]) >= trans(array[i + 1])) {
sum += trans(array[i]);
} else {
sum -= trans(array[i]);
}
}

if (array.length - 1 >= 0) {
sum += trans(array[array.length - 1]);
}

return sum;
}

public int trans(char c) {

switch (c) {
case 'I':
return 1;

case 'V':
return 5;

case 'X':
return 10;

case 'L':
return 50;

case 'C':
return 100;

case 'D':
return 500;

case 'M':
return 1000;

default:
return 0;
}
}
}

We just need to get right number what each character meaning for. And judge the next character implies whether larger than the current character, then we can get it.

Reference
https://leetcode-cn.com/problems/roman-to-integer