递归、DFS感觉好难理解啊

﹏ヽ暗。殇╰゛Y 2021-10-26 15:12 328阅读 0赞

都说递归是一种易于理解的编码方式，但是感觉并没有那么轻松。

今天刷leetCode遇到一个分割回文串的问题，如下：

*给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。*

*返回 s 所有可能的分割方案。*

*示例:*

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

*来源：力扣（LeetCode）*  
*链接：https://leetcode-cn.com/problems/palindrome-partitioning*  
*著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*

其中就有运用DFS和回溯的解法

完整代码如下

package com.LeeCode;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class VariesPalindrome {
        
            List<List<String>>list=new ArrayList<List<String>>();
            String s;
            public List<List<String>> partition(String s) {
        
                //从头到尾递归+回溯。
                this.s=s;
                //这个是满足的每一个集合
                List<String>ll=new ArrayList<String>();
                dfs(ll,0);
                return list;
            }
            public void dfs(List<String>ll,int index){
        
                if(index==s.length())
                {
        
                    list.add(new ArrayList<String>(ll));
                    return;
                }
                //i从index开始是因为单个字符也是回文子串
                for(int i=index;i<s.length();i++)
                {
        
                    //如果是回文
                    if(isPalindrome(index,i)){
        
    
                        //把当前的回文子串s(index,i)加进去
                        ll.add(s.substring(index,i+1));
                        dfs(ll,i+1);
                        //把加进去的回文子串去处。和上面加进去的回文子串是同一个回文子串。
                        ll.remove(ll.size()-1);
                    }
    
                }
            }
            public boolean isPalindrome(int start,int end){
        
                while(start<end){
        
                    if(s.charAt(start)!=s.charAt(end))
                        return false;
                    start++;
                    end--;
                }
                return true;
            }
    
        public static void main(String[] args) {
        
            VariesPalindrome variesPalindrome=new VariesPalindrome();
            String jj="abnnss";
            System.out.println(variesPalindrome.partition(jj));
        }
    }

转载于:https://www.cnblogs.com/heracles-Mercury/p/11068354.html