您的当前位置:首页正文

分割回文的字符串

2024-11-06 来源:个人技术集锦

分割回文的字符串

示例

输入: "aab";
输出: [
  ["aa", "b"],
  ["a", "a", "b"],
];

解题思路

当起点和字符串一样长的时候,说明已经无剩余字符串可以裁剪了,停止,保存路径

	var partition = function (str){
		let ans =[];
		const backTrack =  function(start,path){
			//当起点和字符串一样长的时候,说明已经无剩余的字符串可分割,停止,保存路径
			if(start = str.length){
				ans.push(path)
				return
			}
			for(let i=start,i<start.length;i++){
				let strs = str.slice(start, i+1)
				if(strs && isPalindrome(strs)){
					//其实改为i+1,保存路径的节点 path.concat(strs)
					backTrack(i+1,path.concat(strs)}
			}
		}
		backTrack(0,[])
		return ans
	}
	//判断是否是回文字符串
	function isPalindrome(str){
		return str.split("").reverse().join("") ===str
	}
Top