palindrome-partitioning-ii

11860 단어 LeetCode
제목 연결
사고의 방향
  • 동적 기획을 통해 점 i를 만들기 전에 분할할 수 있는 모든 점 j
  • 이러한 관계를 유방향도로 상상
  • 마지막 노드에서 점 0까지의 최단 경로를 계산한다. - 2 최단 경로는 dijkstra 알고리즘
  • 으로 계산한다.
    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;
         }
    
    }

    좋은 웹페이지 즐겨찾기