ゼロから始めるLeetCode Day88「139. Word Break」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」

次回
ゼロから始めるLeetCode Day89 「62. Unique Paths」

Twitterやってます。

問題

139. Word Break
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、空ではない文字列sと、空ではない単語のリストを含む辞書wordDictが与えられた場合、sが1つ以上の辞書単語のスペースで区切られたシーケンスに分割できるかどうかを判断する、というものです。

Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.

Example 2:

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.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

解法

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True]
        for i in range(1,len(s)+1):
            for j in wordDict:
                if i >= len(j) and s[i-len(j):i] == j and dp[i-len(j)] == True:
                    dp.append(True)
                    break
            if len(dp) <= i:
                dp.append(False)
        return dp[-1]
# Runtime: 28 ms, faster than 98.48% of Python3 online submissions for Word Break.
# Memory Usage: 14 MB, less than 36.33% of Python3 online submissions for Word Break.

よくあるDPの問題だったので仮に条件を満たせばTrueを返すように書いています。
そこまで激烈に難しい問題というよりはきっちり条件付けができるかどうかが重要な問題だと思いました。

にしてもDPっていざ問題にぶつかるとあれ？どうだったっけ？となりがちなのは僕だけでしょうか？
比較的アルゴリズムというよりは考え方の問題、という感じがします。

割と問題をガッツリ解きたい気持ちはあるのでどこかでそういう企画ができたら良さそうですね。

では今回はここまで。お疲れ様でした。