LeetCode 명상: 단어 나누기

이 문제에 대한 설명은 다음과 같습니다.

문자열 s와 문자열 wordDict 사전이 주어지고 s가 하나 이상의 사전 단어로 구성된 공백으로 구분된 시퀀스로 분할될 수 있으면 true를 반환합니다.

참고 사전에 있는 동일한 단어가 분할에서 여러 번 재사용될 수 있습니다.

예:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

또는:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

또는:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

또한 제약 조건은 wordDict의 모든 문자열이 **고유**하며,

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s와 wordDict[i]는 영문 소문자로만 구성됩니다.

---

계속해서 동적 프로그래밍 솔루션을 사용하여 dp 배열을 구축하여 각 인덱스의 wordDict에서 s를 단어로 나눌 수 있는지 추적하는 인기 있는 상향식 접근 방식을 살펴볼 수 있습니다.

각 인덱스 $\mathrm{나는}$나는 dp 배열은 전체 문자열을 인덱스에서 시작하는 단어로 나눌 수 있는지 여부를 나타냅니다. $\mathrm{나는}$나는 .

Note

dp needs to be of size s.length 1 to hold the edge case of an empty string, in other words, when we're out of bounds.

처음에는 false 값으로 만들어 보겠습니다.

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

마지막 인덱스는 깨지기 쉬운, 즉 유효한 것으로 간주될 수 있는 빈 문자열입니다.

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

뒤로 가면 s의 각 인덱스에 대해 해당 인덱스부터 wordDict의 단어에 도달할 수 있는지 확인할 수 있습니다.

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

아직 s(i word.length <= s.length) 범위 내에 있고 단어(s.slice(i, i word.length) === word)를 찾으면 해당 슬롯을 문자열을 분리할 수 있는 "다음 위치"의 진리값으로 표시합니다. i word.length:

let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds




<p>wordDict에서 <em>어떤</em> 단어로 나눌 수 있다면 다른 단어를 계속 볼 필요가 없으므로 루프에서 벗어날 수 있습니다.<br>
</p>

<pre class="brush:php;toolbar:false">dp[s.length] = true; // base case

마지막으로 dp[0]을 반환합니다. 전체 문자열이 wordDict에서 단어로 분리될 수 있으면 해당 값은 true를 저장하고, 그렇지 않으면 false를 저장합니다.

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    /* ... */
  }
}

최종 해결책은 다음과 같습니다.

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    /* ... */
  }
}

시간과 공간의 복잡성

시간복잡도는 $오(n*m*t)$O(n*m*t) 어디 $n$n 문자열은 s이고, $m$m wordDict의 단어 수입니다. $t$t 는 wordDict의 최대 길이 단어입니다. s의 각 문자에 대해 word.length를 사용하는 슬라이스 작업으로 wordDict의 각 단어를 실행하는 중첩 루프가 있기 때문입니다.

공간 복잡도는 $O(n)$O(n) s의 각 인덱스에 대해 저장하는 dp 배열 때문입니다.

---

시리즈의 마지막 동적 계획법 문제는 최장 증가 부분 수열입니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 단어 나누기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!