問題
検索窓に、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面接での聞かれ方
面接では、
- 「文字列と
単語の 辞書が あります。 辞書の 単語だけで 文字列を 区切れるか 判定してください」 - 最初に
再帰で 書くと、 「同じ 位置から 何度も 調べていませんか？」と、 重なりに 気づけるかを 聞かれます - 「区切り方を
全部返すには どうしますか？」と、 答えの 数が 増える 続きを 聞かれる こともあります
同じ
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
まず
段 2
候補をs のok[j] にok[0] はtrue です。ok[j] は、ok[i] が true で、true です。
段 3
辞書はsize をj - size から j のtrue なので、
解答
Python
Python
def can_segment(s, words):
have = set(words)
size = max(map(len, words))
n = len(s)
ok = [False] * (n + 1)
ok[0] = True
for j in range(1, n + 1):
lo = max(0, j - size)
for i in range(lo, j):
if not ok[i]:
continue
if s[i:j] in have:
ok[j] = True
break
return ok[n]JavaScript
JavaScript
function canSegment(s, words) {
const have = new Set(words);
let size = 0;
for (const w of words) {
if (w.length > size) {
size = w.length;
}
}
const n = s.length;
const ok = Array(n + 1)
.fill(false);
ok[0] = true;
for (let j = 1; j <= n; j++) {
let i = j - size;
if (i < 0) i = 0;
for (; i < j; i++) {
if (!ok[i]) continue;
const w = s.slice(i, j);
if (have.has(w)) {
ok[j] = true;
break;
}
}
}
return ok[n];
}Go
Go
func canSegment(
s string, words []string,
) bool {
have := map[string]bool{}
size := 0
for _, w := range words {
have[w] = true
size = max(size, len(w))
}
n := len(s)
ok := make([]bool, n+1)
ok[0] = true
for j := 1; j <= n; j++ {
lo := max(0, j-size)
for i := lo; i < j; i++ {
if ok[i] && have[s[i:j]] {
ok[j] = true
break
}
}
}
return ok[n]
}ok[i] が false の i は、size 文字です。
計算量
- 時間は O(n × L × L) です (n は
sの長さ、 L は いちばん長い 単語の 長さ)。 j ごとに i を L 通り試し、 そのたびに 長さ L までの 文字列を 切り出して 辞書を 引きます。 辞書を 集合に 入れるのに、 単語の 文字数の 合計の 時間も かかります - 使う
記憶は O(n) と、 辞書の 集合の 分です。 表 okの長さが n + 1 です - i を
絞らずに 0 から 試すと、 時間は O(n³) です。 メモの 無い 再帰は、 "aaaa…ab"のような文字列と a、aa、aaaの辞書で、 指数の 時間が かかります
よく
- 欲張りで切る。
前から 辞書に ある 単語が 見つかったら すぐ 切る 書き方は、 例 2 で falseを返します。 どこで 切るかは、 全部の 候補を 表で 確かめます ok[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 が 残るように 外れます。 前から j 文字が 区切れるかを 表にし、 区切れる i から j までが 辞書の 単語なら j も 区切れる、と 前から 埋めます。 辞書は 集合にし、 i は いちばん長い 単語の 長さの 分だけ 戻って 試すので、 時間は O(n × L × L)、 記憶は O(n) です。」
書き終えたら、
「例 2 の
sunsetupでたどります。 前から 3 文字の sun で ok[3]がtrueです。6 文字までは、 sunset その ものと、 sun の あとの set の どちらでも trueです。8 文字までは、 sunset の あとの up は 辞書に 無い ものの、 sun の あとの setup が あるので ok[8]がtrueになり、 答えは trueです。」