题目
给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是回文串。返回s
所有可能的分割方案。
输入: s = "aab" 输出: [["a","a","b"],["aa","b"]]
思路一
我们声明一个res变量用于存放返回结果,在声明一个isValid函数用于判断str形参字符串是否为回文字符串,然后在该函数中判断当前str形参字符串长度是否为1,如果是则直接返回true,如果不是则声明一个l变量作为起始位置,在声明一个r变量作为str形参字符串的最后末端位置,我们接下来进行循环,循环条件为l变量小于r变量,在循环中我们判断当前的str字符串l变量位置在str形参字符串中的字符和末端位置在str形参字符串中的位置是否不相等,如果是则返回false,如果不是则继续循环,并将l变量值自增1,r变量值自减1,逐渐往中间值靠拢,最后循环结束后如果没有返回false则直接返回true,接下来声明递归函数dfs,在函数中声明一个开始值和一个存储结果的数组,然后我们判断当前开始的值和s形参字符串的长度是否相等,如果相等则将arr数组使用push方法添加到res数组中,在直接return出去,如果不相等,那么我们就先声明一个temp空字符串,在使用循环对形参s字符串进行循环,初始的循环值为start变量值,在循环中我们将当前循环字串的值与temp变量字符串进行相加,在使用isValid方法判断temp变量字符串是否是回文字符串,如果是则进行下一轮递归,接下来我们调用递归,最后将res数组返回出去即可
var partition = function(s) { const res = [] function isValid(str) { if(str.length === 1) { return true } let l = 0,r = str.length-1 while(l<r){ if(str[l] !== str[r]) return false l++ r-- } return true } const dfs = (start,arr) => { if(start === s.length){ res.push(arr) return } let temp ='' for(let i =start;i<s.length;i++){ temp+=s[i] if(isValid(temp)){ dfs(i+1,[...arr,temp]) } } } dfs(0,[]) return res };