1. 验证回文串
题目描述： 输入一个字符串，只关注字母和数字，判断字符串是否为回文串。空字符串也可以认为是回文串
image.png
解题思路
关键函数： Character.isLetterOrDigit()判断字符是否为数字或字母
" ".toLowerCase()将字符串中的大写字母全部变为小写字母
- 设置前后两个坐标值 i 和 j
- 先判断是否为字母和数字
如果不是 i++ 或者 j-- - 如果是，则判断两者是否相等，不相等直接返回false；
- 如若全部相等则返回true；
public boolean isPalindrome(String s) {
if(s.length() == 0)
return true;
int len = s.length();
int i = 0;
int j = len - 1;
while(i<j&&i<len&&j>=0){
while(!Character.isLetterOrDigit(s.charAt(i))&&i<j){
i++;
}
while(!Character.isLetterOrDigit(s.charAt(j))&&i<j){
j--;
}
if(!s.substring(i,i+1).toLowerCase().equals(s.substring(j,j+1).toLowerCase())&&i<j){
return false;
}
i++;
j--;
}
return true;
}
分割回文串
题目描述：
image.png
解题思路:
- 从0-i进行判断，如果0-j为回文串，则压入0-j，继续判断j-i是否为回文串
- 直到判断到最后一个字符，就将生成的新的分割方法存入result中
List<List<String>> result = new ArrayList<>();
String s;//对象变量，方便存储
public List<List<String>> partition(String s) {
if(s.length()==0)
return result;
this.s = s;//存储对象变量
function(0,new ArrayList<>());
return result;
}
public boolean isValid(int begin,int end){
while(begin < end){
if(this.s.charAt(begin) != this.s.charAt(end))
return false;
begin++;
end--;
}
return true;
}
public void function(int index,List<String> list){
if(index > (s.length()-1))
{
//一次排序完成
this.result.add(new ArrayList<>(list));
}
for(int i = index; i < s.length();i++){
if(isValid(index,i)){
list.add(this.s.substring(index,i+1));
function(i+1,list);
list.remove(list.size()-1);
}
}
}
3. 单词拆分
题目描述：
image.png
image.png
public boolean wordBreak(String s, List<String> wordDict) {
//动态规划的解法
if(s == null || s.length() == 0)
return true;
boolean res[] = new boolean[s.length()+1];//res[i]代表了从1-i个字符可以用字典中的词来填充
res[0] = true;//第0个默认为true
for(int i = 0; i < s.length();i++){
StringBuilder builder = new StringBuilder(s.substring(0,i+1));//从下标为0到下标为i的字符串，也就是第i+1个字符
for(int j = 0; j<=i;j++){
if(res[j]&&wordDict.contains(builder.toString())){
res[i+1] = true;
//这里的第res[i+1]代表了前i 个字符可以用字典中的单词代替
//第1-j个字符为true，同时j+1到i+1的字符串在字典里面;
break;
}
builder.deleteCharAt(0);//删除前j个字符
}
}
return res[s.length()];
}
4. 单词拆分Ⅱ
题目描述：
image.png
示例
思路：
动态规划，每次截取字符串前方一部分字符串，判断字典中是否存在。
如果存在，则记录当前单词，并继续判断之后的字符
v1.0实现代码
class Solution {
List<String> result;
String s;
public List<String> wordBreak(String s, List<String> wordDict) {
result = new ArrayList<>();
this.s = s;//创建返回值和保存字符串常量
cutWords(0,wordDict,new ArrayList<>());
return result;
}
public void cutWords(int index,List<String> wordDict,List<String> save){
/**
*
参数说明，index表示还未处理的最前下标，wordDice字典,save暂时保存的数据
*/
if(index >= s.length()){
//已经找到了个划分方法
StringBuilder builder = new StringBuilder();
for(int i = 0; i < save.size()-1;i++){
builder.append(save.get(i));
builder.append(" ");
}
builder.append(save.get(save.size()-1));//最后一个单词
result.add(builder.toString());
}
else{
for(int i = index;i < s.length();i++){
StringBuilder builder = new StringBuilder(s.substring(index,i+1));
if(wordDict.contains(builder.toString())){
save.add(builder.toString());
cutWords(i+1,wordDict,save);
save.remove(save.size()-1);
}
}
}
}
}
出现的问题： 在某些用例中会出现超时的错误
超时
这就要用到剪枝，在进行动态规划之前，首先判断当前是否能够进行单词划分
v 2.0
class Solution {
List<String> result;
String s;
public List<String> wordBreak(String s, List<String> wordDict) {
result = new ArrayList<>();
this.s = s;//创建返回值和保存字符串常量
//加入剪枝
boolean []judge = new boolean[s.length()+1];
judge[0] = true;
for(int i = 0; i < s.length();i++){
for(int j = 0; j <= i;j++){
if(judge[j]&&wordDict.contains(s.substring(j,i+1))){
judge[i+1] = true;
break;
}
}
}
if(!judge[s.length()]){
return result;
}
cutWords(0,wordDict,new ArrayList<>());
return result;
}
public void cutWords(int index,List<String> wordDict,List<String> save){
/**
*
参数说明，index表示还未处理的最前下标，wordDice字典,save暂时保存的数据
*/
if(index >= s.length()){
//已经找到了个划分方法
StringBuilder builder = new StringBuilder();
for(int i = 0; i < save.size()-1;i++){
builder.append(save.get(i));
builder.append(" ");
}
builder.append(save.get(save.size()-1));//最后一个单词
result.add(builder.toString());
}
else{
for(int i = index;i < s.length();i++){
StringBuilder builder = new StringBuilder(s.substring(index,i+1));
if(wordDict.contains(builder.toString())){
save.add(builder.toString());
cutWords(i+1,wordDict,save);
save.remove(save.size()-1);
}
}
}
}
}
总结
对于字符串的题目，要记录的是几个关键的函数与ASCII码范围
- 变大小写的函数
"".toLowerCase(); //字符串变小写
"".toUpperCase(); //字符串变大写
- 判断是否是字母或数字
''.isLetter(); //判断是否是字母
''.isDigit(); //判断是否是数字
''.isLetterOrDigit();//判断是否是数字或字母
- 字符串和字符数组之间的相互转换
String str = "";
str.toCharArray(); //String 转化为char数组
- ASCII码
大写字母： 'A' 65
小写字母：'a' 97
数字：'0' 48
