珠海微网站建设,珠海网站推广优化,婚恋网站的架构,锋创科技园网站建设题目#xff1a;给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文串。返回 s 所有可能的分割方案。
思路#xff1a;
第一步#xff1a;确定参数与返回值。参数为字符串s#xff0c;分割起始下标startIndex#xff0c;无返回值
第二…题目给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串。返回 s 所有可能的分割方案。
思路
第一步确定参数与返回值。参数为字符串s分割起始下标startIndex无返回值
第二步确定终止条件。当startIndexs.length()说明找到了一组分割方案将其加入结果集
第三步确定单层递归逻辑。for循环遍历s字符串从startIndex到s.length()-1。如果[startIndex,i]的区间下标组成的字符串是回文串则将该字符串加入path否则跳过本轮循环。接着递归回溯
代码 public ListListString resultnew ArrayList();public ListString pathnew ArrayList();public ListListString partition(String s) {backTracking(s,0);return result;}public void backTracking(String s,int startIndex){//如果startIndex切割线到最后一个元素则收集到一个回文串if(startIndexs.length()){result.add(new ArrayList(path));return;}for(int istartIndex;is.length();i){//如果是回文串则记录if(isPalindrome(s,startIndex,i)){String strs.substring(startIndex,i1);path.add(str);}elsecontinue;//递归回溯backTracking(s,i1);path.remove(path.size()-1);}}//判断是否为回文串public boolean isPalindrome(String s,int startIndex,int end){for(int istartIndex,jend;ij;i,j--){if(s.charAt(i)!s.charAt(j))return false;}return true;}
