단어 분할 golang 실현
s wordDict, s 。
:
。
。
1:
: s = "leetcode", wordDict = ["leet", "code"]
: true
: true "leetcode" "leet code"。
2:
: s = "applepenapple", wordDict = ["apple", "pen"]
: true
: true "applepenapple" "apple pen apple"。
。
3:
: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
: false
사고의 방향
1.
dp[i] i
dp[i] = true s[0:j] s[j:i]
s[0:j] dp[j] = true
s[j:i]
dp[i] = dp[j] && s[j:i] in wordDict
이루어지다
func wordBreak(s string, wordDict []string) bool {
l := len(s)
dict := make(map[string]bool)
dp := make([]bool, l+1)
dp[0] = true
for _, word := range wordDict{
dict[word] = true
}
dict[""] = true
for i := 0; i <= l; i++{
for j :=0; j <= i; j++{
if _, ok := dict[s[j:i]];ok && dp[j] {
dp[i] = true
}
}
}
return dp[l]
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.