怎么做垂直网站,dede生成网站地图,wordpress 文章rss,注册公司需要什么条件才可以文章目录 131. 分割回文串题目描述回溯代码 131. 分割回文串
题目描述
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1#xff1a; 输入#xf… 文章目录 131. 分割回文串题目描述回溯代码 131. 分割回文串
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1 输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2 输入s “a” 输出[[“a”]] 提示
1 s.length 16s 仅由小写英文字母组成
回溯代码
在此代码片段中子字符串是通过递归函数 backtracking 来获取的。函数 backtracking 是一个回溯算法的实现用于找到字符串 s 的所有可能的回文分割。回文分割是指将字符串分割成若干子串使得每个子串都是回文的。
下面是 backtracking 函数在寻找子串时的详细过程 函数 backtracking 接收原始字符串 s 和一个 startIndex 参数该参数指示当前考虑的子串的起始位置。 在每一层递归中函数通过循环从 startIndex 遍历到字符串 s 的末尾。 在每次迭代中它通过调用 isPalindrome 函数来检查当前考虑的子串 s[startIndex, i] 是否是回文。 如果检测到子串是回文使用 substr 方法从 s 中提取出回文子串。substr 方法的第一个参数是子串的起始位置第二个参数是要提取的字符数。这里提取的字符数计算为 i - startIndex 1表示从 startIndex 到 i包含 i的子串长度。 获取到的回文子串 str 被加入到临时路径 path 中。 然后递归调用 backtracking 函数在寻找剩余子串的新的回文分割方案此时 startIndex 更新为 i 1因为 i 位置的字符已经包含在了当前找到的回文子串内。 递归返回后执行 path.pop_back()这是回溯的一部分它将最后一个添加到 path 中的回文子串移除以便 path 可以用于下一次循环迭代时的新的分割方案。 当 startIndex 大于或等于字符串 s 的长度时意味着已经到达字符串的末尾当前 path 中存储的回文子串序列即为 s 的一个有效分割此时将 path 加入到 result 中。
通过这种方法代码实现了在递归循环中对字符串进行子串的分割并确保了每个分割方案中的所有子串都是回文的。
假设我们有一个字符串 s “aab” 并且我们想要找到所有可能的回文分割方案。下面是 backtracking 函数在这个字符串上操作的示例 初始调用 backtracking(aab, 0)startIndex 是 0意味着我们从字符串的第一个字符开始。 第一层递归的循环从 i 0 开始 a. 检查子串 s[0, 0] 即 a 是否是回文 — 是所以 path 变为 [a]。 b. 递归调用 backtracking(aab, 1) 查看从第二个字符开始的所有回文分割方案。 第二层递归开始现在考虑的子串是 ab a. 循环从 i 1 开始检查子串 s[1, 1] 即 a 是否是回文 — 是所以现在 path 变为 [a, a]。 b. 递归调用 backtracking(aab, 2) 查看从第三个字符开始的所有回文分割方案。 第三层递归开始现在考虑的子串是 b a. 循环从 i 2 开始检查子串 s[2, 2] 即 b 是否是回文 — 是所以现在 path 变为 [a, a, b]。 b. 递归调用 backtracking(aab, 3)发现 startIndex 等于字符串长度意味着找到了完整的一组分割方案。将其添加到 result 中result [[a, a, b]]。 c. 回溯发生path.pop_back() 移除最后一个元素 b现在 path [a, a]。 返回到第二层递归继续 i 的循环现在 i 2 a. 检查子串 s[1, 2] 即 ab 是否是回文 — 不是所以不改变 path。 b. 循环结束开始回溯path.pop_back() 移除最后一个元素 a现在 path [a]。 返回到第一层递归继续 i 的循环下一次 i 1 a. 检查子串 s[0, 1] 即 aa 是否是回文 — 是所以 path 变为 [aa]。 b. 递归调用 backtracking(aab, 2) 查看从第三个字符开始的所有回文分割方案。 第四层递归开始现在考虑的子串是 b a. 循环从 i 2 开始检查子串 s[2, 2] 即 b 是否是回文 — 是所以 path 变为 [aa, b]。 b. 递归调用 backtracking(aab, 3)发现 startIndex 等于字符串长度意味着找到了另外一个完整的一组分割方案。将其添加到 result 中现在 result [[a, a, b], [aa, b]]。 回溯发生path.pop_back() 移除 b回到 path [aa]。然后第四层递归的循环结束path.pop_back() 再次移除 aa回到 path []。
最终的 result 包含了所有可能的回文分割方案[[a, a, b], [aa, b]]。这样我们就逐步构建了每一个可能的回文分割方案并将有效的方案添加到结果集中。 class Solution {
public:// 主函数调用回溯函数并返回结果vectorvectorstring partition(string s) {backstracking(s,0); // 从字符串的第一个字符开始进行回溯return result; // 返回所有可能的分割方案}private:vectorvectorstring result; // 存储所有可能的分割方案vectorstring path; // 用于存储当前的分割方案// 检查一个子串是否是回文串bool cheak(string s,int begin,int end) {for(int ibegin,jend;ij;i,j--) // 从两头开始向中间检查if(s[i]!s[j]) // 如果两头字符不相等则不是回文return false; // 返回 falsereturn true; // 所有字符都相等返回 true}// 回溯函数void backstracking(string s,int start) {if(starts.size()) { // 如果 start 等于字符串的长度表示已经处理完毕result.push_back(path); // 将当前的分割方案添加到结果中return ; // 返回上一层}// 从 start 开始往后查找可能的分割点for(int istart;is.size();i) {if(cheak(s,start,i)) { // 检查从 start 到 i 的子串是否是回文string strs.substr(start,i-start1); // 是将其作为一个分割path.push_back(str); // 将子串添加到当前的分割方案中} else {continue; // 如果不是回文跳过当前的字符继续下一轮循环}backstracking(s,i1); // 递归调用从下一个字符开始继续分割剩余的字符串path.pop_back(); // 回溯移除最后添加的子串尝试其他可能的分割点}}
};
