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
• 1
• 1
• 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

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

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

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 



<h4>
  
  
  시간과 공간의 복잡성
</h4>

<p>시간복잡도는 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>오</mi><mo stretchy="false">(</mo><mi>n</mi><mo>*</mo><mi>m</mi><mo>*</mo><mi>t</mi><mo stretchy="false">)</mo></mrow>O(n * m * t) </semantics></math><span><span>O(n*</span><span>m*</span><span>t)</span></span></span>
</span>
 어디 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow>n </semantics></math><span><span>n</span></span></span>
</span>
 문자열은 s이고, 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow>m</semantics></math><span><span>m</span></span></span>
</span>
 wordDict의 단어 수입니다. 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow>t </semantics></math><span><span>t</span></span></span>
</span>
 는 wordDict의 최대 길이 단어입니다. s의 각 문자에 대해 word.length를 사용하는 슬라이스 작업으로 wordDict의 각 단어를 실행하는 중첩 루프가 있기 때문입니다.</p>

<p>공간 복잡도는 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow>O(n) </semantics></math><span><span>O(n)</span></span></span>
</span>
 s의 각 인덱스에 대해 저장하는 dp 배열 때문입니다.</p>


<hr>

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


          

            
  

            
        

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