用凡科帮别人做网站,乐平网站设计,怎么免费建网站,wordpress大前端1.9目录 验证回文串题目描述题目分析cpp代码 131. 分割回文串题目描述题目分析cpp代码 验证回文串
题目#x1f517;
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字… 目录 验证回文串题目描述题目分析cpp代码 131. 分割回文串题目描述题目分析cpp代码 验证回文串
题目
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
题目分析
这题主要问题在于包含非字母/数字字符比如 、,、:等所以我们要把这些情况考虑进去。
cpp代码
class Solution {
public:bool isPalindrome(string s) {int i 0;int j s.size()-1;while(i j){while(i j !(isdigit(s[i]) || isalpha(s[i]))) i;while(i j !(isdigit(s[j]) || isalpha(s[j]))) j--;if(tolower(s[i]) tolower(s[j])){i; j--;}else return false;}return true;}
};这里用了几个C库函数方便我们处理
isdigit(x)判断x是否是数字isalpha(x)判断x是否是字母tolower(x)将大写字母转换成小写字母如果本身是非字母字符则不变。
131. 分割回文串
题目
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
题目分析
其实切割问题和组合问题本质上是一样的我们将int startIndex当作上一次的分割结束点横向是从startIndex到i这个区间切割的可能情况纵向是针对每一种可情况的startIndex到i切割再从i1开始向后分割即i1就是上一次的分割结束点。
每次分割时可以判断当前startIndex到i是不是回文字符串如果是则将当前分割结果放入path中如果不是就continue去看下一个startIndex到i。
cpp代码
class Solution {
public:vectorstring path;vectorvectorstring result;bool isPalindrome(string s, int i, int j) {// int i 0;// int j s.size()-1;while(i j){while(i j !(isdigit(s[i]) || isalpha(s[i]))) i;while(i j !(isdigit(s[j]) || isalpha(s[j]))) j--;if(tolower(s[i]) tolower(s[j])){i; j--;}else return false;}return true;}void backtracking(int startIndex, const string s){// 终止条件if(startIndex s.size()){ // 当startIndex超出s大小则放结果result.push_back(path);return;}for(int i startIndex; i s.size(); i){if(isPalindrome(s, startIndex, i)){ // 如果当前切割是回文串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);}else continue;backtracking(i 1, s);path.pop_back();}}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(0, s);return result;}
};
