動的計画法で 文字列を 辞書の 単語に 区切れるか調べる - LeetCode 139
空白の
海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)
問題
検索窓に、s がwords をs をtrue、false を
- 辞書の
同じ 単語を 何回使っても 構いません。 使わない 単語が あっても 構いません sの長さは 1 以上 300 以下です wordsの長さは 1 以上 1000 以下で、 単語は どれも 違います。 単語の 長さは 1 以上 20 以下です - 文字は
英小文字だけです
入力と出力の例
例 1
ice、
入力
s = "icecreamcone"
words = ["cone", "ice", "cream"]出力
true例 2
前から sun、
入力
s = "sunsetup"
words = ["sun", "set", "sunset",
"setup"]出力
true例 3
tea、
入力
s = "teapotlid"
words = ["tea", "teapot", "pot",
"lids"]出力
false図で見る
例 1 で、
面接での聞かれ方
面接では、
- 「文字列と
単語の 辞書が あります。 辞書の 単語だけで 文字列を 区切れるか 判定してください」 - 最初に
再帰で 書くと、 「同じ 位置から 何度も 調べていませんか?」と、 重なりに 気づけるかを 聞かれます - 「区切り方を
全部返すには どうしますか?」と、 答えの 数が 増える 続きを 聞かれる こともあります
同じ
ヒント
まだ開いていません
付箋は 3 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3答えに近い
アルゴリズムのチートシートの「動的計画法 (DP)」に、
関わる学び
動的計画法は、
まず 考える手順
段 1
まず
段 2
候補をs のend 文字はcan_break[end] にcan_break[0] はtrue です。can_break[end] は、start にcan_break[start] が true で、start 文字目のend 文字目までがtrue です。
段 3
辞書はstart は end から 20 文字よりlongest をstart を end - longest から end のend はtrue なので、start は
解答
Python
Python
def can_segment(
s: str, words: list[str]
) -> bool:
word_set = set(words)
longest = max(map(len, words))
can_break = [False] * (len(s) + 1)
can_break[0] = True
for end in range(1, len(s) + 1):
earliest = max(0, end - longest)
for start in range(
earliest, end
):
if not can_break[start]:
continue
if s[start:end] in word_set:
can_break[end] = True
break
return can_break[len(s)]JavaScript
JavaScript
function canSegment(s, words) {
const wordSet = new Set(words);
const longest = Math.max(
...words.map((word) => word.length)
);
const canBreak = Array(s.length + 1)
.fill(false);
canBreak[0] = true;
for (
let end = 1;
end <= s.length;
end++
) {
const earliest =
Math.max(0, end - longest);
for (
let start = earliest;
start < end;
start++
) {
if (!canBreak[start]) {
continue;
}
const piece = s.slice(start, end);
if (wordSet.has(piece)) {
canBreak[end] = true;
break;
}
}
}
return canBreak[s.length];
}Go
Go
func canSegment(
s string, words []string,
) bool {
wordSet := map[string]bool{}
longest := 0
for _, word := range words {
wordSet[word] = true
longest = max(longest, len(word))
}
canBreak := make([]bool, len(s)+1)
canBreak[0] = true
for end := 1; end <= len(s); end++ {
earliest := max(0, end-longest)
start := earliest
for ; start < end; start++ {
piece := s[start:end]
if canBreak[start] &&
wordSet[piece] {
canBreak[end] = true
break
}
}
}
return canBreak[len(s)]
}can_break[start] が false の start は、longest 文字です。
計算量
- 時間は O(n × L × L) です (n は
sの長さ、 L は いちばん長い 単語の 長さ)。 endごとにstartを L 通り試し、そのたびに 長さ L までの 文字列を 切り出して 辞書を 引きます。 辞書を 集合に 入れるのに、 単語の 文字数の 合計の 時間も かかります - 使う
記憶は O(n) と、 辞書の 集合の 分です。 表 can_breakの長さが n + 1 です startを絞らずに 0 から 試すと、 時間は O(n³) です。 メモの 無い 再帰は、 "aaaa…ab"のような文字列と a、aa、aaaの辞書で、 指数の 時間が かかります
よく ある間違い
- 欲張りで切る。
前から 辞書に ある 単語が 見つかったら すぐ 切る 書き方は、 例 2 で falseを返します。 どこで 切るかは、 全部の 候補を 表で 確かめます can_break[0]をfalseにする。 空の前置きは 区切れている、が 土台です。 ここを 忘れると、 どの 位置も trueにならず、いつも falseを返します- 辞書を
並びのまま引く。 wordsの並びの 中から 毎回探すと、 1 回の 引きに 辞書の 長さ分の 時間が かかります。 1000 語の 辞書では 大きく 遅くなるので、 集合にします - メモの
無い 再帰で書く。 s = "aaa…ab"で辞書が a、aa、aaaだと、最後の b で 必ず失敗するのに、 区切り方を 全部試して 時間切れに なります。 同じ 位置からの 答えを 覚えておく 必要があります
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での 話し方の例
書き始める
「欲張りで
切ると、 sunsetup を sun、 set や sunset と 切って up が 残るように 外れます。 前から 何文字までが 区切れるかを 表にし、 区切れる 位置からいまの 位置までが 辞書の 単語なら、 いまの 位置も 区切れる、と 前から 埋めます。 辞書は 集合にし、 始まりは いちばん長い 単語の 長さの 分だけ 戻って 試すので、 時間は O(n × L × L)、 記憶は O(n) です。」
書き終えたら、
「例 2 の
sunsetupでたどります。 前から 3 文字の sun で can_break[3]がtrueです。6 文字までは、 sunset その ものと、 sun の あとの set の どちらでも trueです。8 文字までは、 sunset の あとの up は 辞書に 無い ものの、 sun の あとの setup が あるので can_break[8]がtrueになり、 答えは trueです。」