[PYTHON] Let Code Day 88 "139. Word Break" starting from scratch

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day87 starting from zero "1512. Number of Good Pairs"

Twitter I'm doing it.

** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!

problem

139. Word Break The difficulty level is Medium. This is an excerpt from Leet Code 60 Questions I Want to Solve for Coding Interview Preparation.

The problem is that given a non-empty string s and a dictionary wordDict containing a list of non-empty words, s is in a space-separated sequence of one or more dictionary words. It's about determining if it can be split.

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

solution

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.

Since it was a common DP problem, I wrote that it returns True if the conditions are met. I think it's more important to be able to condition properly than to be such an extremely difficult problem.

But what if DP hits a problem? How was it? Am I the only one who tends to be next to me? I feel that it is a matter of thinking rather than an algorithm.

I have a desire to solve the problem relatively well, so it would be nice if such a project could be done somewhere.

So that's it for this time. Thank you for your hard work.