字符串题

125 验证回文串

左指针 右指针

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 boolean isPalindrome(String s) {
if(s.length() == 0)
return true;
int l = 0, r = s.length() - 1;
while(l < r){
//确定指定的字符是否为字母或数字
if(!Character.isLetterOrDigit(s.charAt(l))){
l++;
}else if(!Character.isLetterOrDigit(s.charAt(r))){
r--;
}else{
if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
l++;
r--;
}
}
return true;
}
}

131 分割回文串

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

class Solution {
List<List<String>> res = new ArrayList<>();

public List<List<String>> partition(String s) {
if(s==null||s.length()==0)
return res;
dfs(s,new ArrayList<String>(),0);
return res;
}

public void dfs(String s,List<String> remain,int left){
if(left==s.length()){ //判断终止条件
res.add(new ArrayList<String>(remain)); //添加到结果中
return;
}
for(int right=left;right<s.length();right++){ //从left开始,依次判断left->right是不是回文串
if(isPalindroom(s,left,right)){ //判断是否是回文串
remain.add(s.substring(left,right+1)); //添加到当前回文串到list中
dfs(s,remain,right+1); //从right+1开始继续递归,寻找回文串
remain.remove(remain.size()-1); //回溯,从而寻找更长的回文串
}
}
}
/**
* 判断是否是回文串
*/
public boolean isPalindroom(String s,int left,int right){
while(left<right&&s.charAt(left)==s.charAt(right)){
left++;
right--;
}
return left>=right;
}
}

139 单词拆分

动态规划

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 boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
int max_length=0;
for(String temp:wordDict){
max_length = temp.length() > max_length ? temp.length() : max_length;
}
// memo[i] 表示 s 中以 i - 1 结尾的字符串是否可被 wordDict 拆分
boolean[] memo = new boolean[n + 1];
memo[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i-1; j >= 0 && max_length >= i - j; j--) {
if (memo[j] && wordDict.contains(s.substring(j, i))) {
memo[i] = true;
break;
}
}
}
return memo[n];
}
}

344 反转字符串

从两头往中间走

1
2
3
4
5
6
7
8
9
10
11
12
13
14


class Solution {
public:
string reverseString(string s) {
int i = 0, j = s.size() - 1;
while (i < j){
swap(s[i],s[j]);
i++;
j--;
}
return s;
}
};

字符串转换为整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19


public class Solution {
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (i == 0 && (c == '+' || c == '-')) /* 符号判定 */
continue;
if (c < '0' || c > '9') /* 非法输入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}