palindrome-partitioning-ii
11860 단어 LeetCode
사고의 방향
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
public class Solution {
//
public int minCut(String s) {
if(s==null ||s.length()==0){
return 0;
}
//
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
int[] dp = new int[s.length()+1];// 0--i
dp[0] = 1;
ArrayList<Integer> list0 = new ArrayList<Integer>();
list0.add(-1);
list.add(list0);
for(int i=1;i<dp.length;i++){
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int j=0;j<i;++j){
if(dp[j]==1 && isPalindrome(s.substring(j,i))){
dp[i] =1;
temp.add(j);
}
}
list.add(temp);
}
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
ArrayList<String> curList = new ArrayList<String>();
// dfs(s,curList,list.size()-1,list,result);
//
int[][] map = new int[s.length()+1][s.length()+1];
for(int i=0;i<map.length;i++){
for(int j=0;j<map.length;++j){
map[i][j] = Integer.MAX_VALUE;
}
}
for(int i=0;i<list.size();i++){
for(int j=0;j<list.get(i).size();++j){
if(list.get(i).get(j)>=0) map[i][list.get(i).get(j)] = 1;
}
}
ArrayList<Integer> minRoute = getTwoPointsRoute( map.length-1,0, map);
//System.out.println(minRoute.size()-2);
return minRoute.size()-3;
}
public static ArrayList<Integer> getTwoPointsRoute(int start,int end,int[][]map){
int cur = end;
int maxMapPoints = map.length;
int[] dist = new int[maxMapPoints];
int[] prev = new int[maxMapPoints];
int mapPoints = map.length;
if(start<0 || start>mapPoints || cur<0 || cur>mapPoints || prev[cur]==-1){
return null;
}
ArrayList<Integer> arrayList = new ArrayList<Integer>();
DijkstraMethod(start, dist, prev, map);
Stack<Integer> stack = new Stack<Integer>();
int cost = 0;
while(cur!=-1){
//System.out.print(cur+" ");
stack.add(cur);
cost += dist[cur];
cur = prev[cur];
}
//
while(!stack.isEmpty()){
arrayList.add(stack.pop());
}
arrayList.add(cost);
return arrayList;
}
public static void DijkstraMethod(int v0,int[] dist,int[] prev,int[][]map){
int n = map.length;
boolean[] S = new boolean[map.length];// S
//
for(int i =0;i<n;i++){
dist[i] = map[v0][i];
S[i] = false;
if(dist[i]==Integer.MAX_VALUE){
prev[i]= -1;
}else{
prev[i] = v0;
}
}
dist[v0] = 0;
S[v0] = true;
// n-1 S
for(int i=0;i<n-1;i++){
int mindist = Integer.MAX_VALUE;
int u = v0;
// U j u dist[j]
for(int j=0;j<n;j++){
if(!S[j] && dist[j]<mindist){
u = j;
mindist = dist[j];
}
}
S[u] = true;
// U , v0 u U U
for(int j=0;j<n;++j){
if(!S[j] && map[u][j]<Integer.MAX_VALUE){
if(dist[u]+map[u][j]<dist[j]){
dist[j] = dist[u] +map[u][j];
prev[j] = u;
}
}
}
}
}
// public static void dfs(String s,ArrayList<String> curList,int cur,ArrayList<ArrayList<Integer>> list,ArrayList<ArrayList<String>> result){
// if(cur==0){
// Collections.reverse(curList);
// result.add(curList);
// return;
// }
//
// for(int i=list.get(cur).size()-1;i>=0;i--){
//
// int next = list.get(cur).get(i);
// ArrayList<String> temp = new ArrayList<String>();
// temp.addAll(curList);
// curList.add(s.substring(next,cur));
// temp.add(s.substring(next,cur));
// System.out.println("@"+cur+"@"+curList);
// dfs(s,temp,next,list,result);
// curList.remove(curList.size()-1);
// }
// }
public static boolean isPalindrome(String str){
if(str==null || str.length()==0){
return false;
}
for(int i=0,j=str.length()-1;i<=j;i++,j--){
if(str.charAt(i)!=str.charAt(j)) return false;
}
return true;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.