차례차례 DFS 이해하기 힘드네요.

4025 단어
모두 귀속은 이해하기 쉬운 인코딩 방식이라고 말하지만, 그렇게 가볍지는 않다.
오늘 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=new ArrayList>();
String s;
public List> partition(String s) {
// + 。
this.s=s;
//
Listll=new ArrayList();
dfs(ll,0);
return list;
}
public void dfs(Listll,int index){
if(index==s.length())
{
list.add(new ArrayList(ll));
return;
}
//i index
for(int i=index;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
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

좋은 웹페이지 즐겨찾기