動的計画法で文字列を辞書の単語に区切れるか調べる - 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、cream、cone の 3 つに区切れます。

入力

s = "icecreamcone"
words = ["cone", "ice", "cream"]

出力

true

例 2

前から sun、set と切ると、残りの up が辞書にありません。sun、setup と切れば区切れます。

入力

s = "sunsetup"
words = ["sun", "set", "sunset",
  "setup"]

出力

true

例 3

tea、pot や teapot までは辞書にありますが、残りの lid がありません。lids では長すぎます。

入力

s = "teapotlid"
words = ["tea", "teapot", "pot",
  "lids"]

出力

false

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、短い一文で渡され、最初の書き方から速くしていく流れが多いです。

  • 「文字列と単語の辞書があります。辞書の単語だけで文字列を区切れるか判定してください」
  • 最初に再帰で書くと、「同じ位置から何度も調べていませんか?」と、重なりに気づけるかを聞かれます
  • 「区切り方を全部返すにはどうしますか?」と、答えの数が増える続きを聞かれることもあります

同じ単語を何回使えるか、辞書が空のことがあるかは、最初に確かめておきます。この問題では何回でも使えて、辞書は空ではありません。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

main.py
def can_segment(s: str, words: list[str]) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(can_segment("icecreamcone", ["cone", "ice", "cream"]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します