[LeetCode] Word Break II 동적 계획
사전에 있는 모든 단어가 목표 열을 재구성할 수 있는 결과를 찾아야 합니다
public class Solution {
public static List<String> wordBreak(String s, Set<String> dict) {
List<String> dp[] = new ArrayList[s.length()+1];
dp[0] = new ArrayList<String>();
for(int i=0; i<s.length(); i++){
//i
if( dp[i] == null ) continue; //
for(String word:dict){
int len = word.length();
int end = i+len;
if(end > s.length()) continue;
if(s.substring(i,end).equals(word)){
if(dp[end] == null){
dp[end] = new ArrayList<String>();
}
dp[end].add(word);//
}
}
}
List<String> ans = new LinkedList<String>();
if(dp[s.length()] == null) return ans;
ArrayList<String> tmp = new ArrayList<String>();
dfsStringList(dp,s.length(),ans, tmp);
return ans;
}
public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){
if(end <= 0){
String ans = tmp.get(tmp.size()-1);
for(int i=tmp.size()-2; i>=0; i--)
ans += (" " + tmp.get(i) );
res.add(ans);
return;
}
for(String str:dp[end]){
tmp.add(str);
dfsStringList(dp,end-str.length(), res, tmp);
tmp.remove(tmp.size()-1);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.