word-break
1348 단어 Leetcode
[문제풀이 사고방식] 만약에 한 단어에 하나의 분해 방법이 존재하고 분해된 모든 블록이 사전에 있다면 반드시 이러한 조건을 만족시켜야 한다. 이 단어의 마지막 분할점에 대해 이 분할점에서 단어의 끝까지 구성된 문자열은 하나의 단어이고 이 분할점에서 단어의 시작까지 구성된 문자열도 분해할 수 있다.그래서 이 조건을 충족시키기만 하면 우리는 이 긴 문자열도 분해할 수 있다는 것을 확신할 수 있다.그래서 우리는 검증을 기다리는 문자열의 길이를 외부 순환으로 제어하고 내부 순환으로 이러한 분할점을 찾아 문자열을 하나의 단어와 같은 분해 가능한 하위 문자열로 나눌 수 있다.또한, 우리는 문자열의 길이가 증가할 때 분해할 수 있는 상황을 수조로 기록하여 나중에 사용할 수 있도록 하고, 중복 계산을 피한다.
[고사 내용] 동태적 기획, 심도 있는 검색
class Solution {
public:
bool wordBreak(string s, unordered_set &dict) {
//dp[i]: s[0...i] can be egemented in dict
//dp[i] = dp[0][k] && d[k][i]
int len = s.length();
vector dp(len,false);
for(int i = 0; i < len; i++){
if(dict.find(s.substr(0,i+1))!=dict.end()) dp[i]=true;//substr( ， )
for(int j = 1; j <= i; j++){
if((dict.find(s.substr(j,i-j+1))!=dict.end()) && dp[j-1])
dp[i]=true;
}
}
return dp[len-1];
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
