Letcode: 문자열 s와 단어 사전 dict를 지정하여 s를 한 개 이상의 사전 단어로 구성된 빈칸으로 구분할 수 있는지 확인합니다.
For example, givens ="leetcode",dict =["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".
사고방식: 동적 기획법
boolean 수조 dp를 설정합니다. dp[k]는 문자열 s 전 k자로 구성된 문자열이 사전 dict의 서열로 분할될 수 있는지 여부를 나타냅니다. dp[i]는true와 같을 때 분할될 수 있음을 나타냅니다.
문제에서 제시한 예와 같이 s="leetcode", dict=["leet", "code"].
초기 dp[0] = true.
i 1 2 3 4 5 6 7 8
j 0 l le lee leet leetc leetco leetcod leetcode
1 e ee eet eetc eetco eetcod eetcode
2 e et etc etco etcod etcode
3 t tc tco tcod tcode
4 c co cod code
5 o od ode
6 d de
7 e
(1) i=4, j=0일 때 s.substring(i, j)="leet", "leet"은 사전 dict에서 찾을 수 있고 분할될 수 있으며 d[j]=true는 전 j 문자를 대표하는 문자열을 분할할 수 있다(전 하위 문제의 해답은 후 하위 문제의 해답으로 유용한 정보를 제공). 따라서 전 i자 문자열인 "leet"은 분할할 수 있기 때문에 d[i]=true.
(2) i=8, j=4시, s.substring(i, j)="code", "code"는 사전dict에서 찾을 수 있고 분할될 수 있으며, d[j]=true는 앞의 j 문자를 대표하는 문자열을 분할할 수 있다(전의 하위 문제를 뒤의 하위 문제로 풀 수 있는 해답은 유용한 정보를 제공한다. 첫 번째 단계에서 문자열 s 앞의 네 문자로 구성된 문자열 "leet"을 분할할 수 있다). 따라서 앞의 문자열인 "leetcode"는 분할할 수 있다.따라서 d[i] = true
(3) 마지막으로 dp[len]을 되돌려줍니다. 앞의 len 문자로 구성된 문자열이 사전 dict의 서열로 분할될 수 있는지, 즉 전체 문자열이 분할될 수 있는지를 나타냅니다.
Java 코드 구현
import java.util.Set;
public class Solution {
public boolean wordBreak(String s, Set dict) {
int len = s.length();
// false
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for(int i = 1; i <= len; i++){
for(int j = 0; j < i; j++){
if(dp[j] && dict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[len];
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
