차례차례 DFS 이해하기 힘드네요.
오늘 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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.