Apr 27, 2021

Leetcode 139 Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.


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



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.



Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
  • Bu soruda bize bir kelime(s) ve liste halinde bir kelimeler içeren bir sözlük(wordDict) veriliyor.
  • Bizden istenen ise kelime(s) sözlükteki kelimelerden oluşuyor ise True oluşmuyor ise False olarak dönmemiz.
  • Input: s = “leetcode”, wordDict = [“leet”,“code”] şeklinde girdilerimiz olsun.
  • s kelimesindeki her indexi uyumlu kelime var mı diye inceleyelim.
  • dp[8] = True -> s kelimemiz 8 harften oluşuyor yani dp[8] kelimenin bittiği boşluğa denk geliyor.Ama tüm s kelimesini başarılı bir şekilde bitirip sona varsaydık True dönecektik bundan dolayı True dedik.Ayrıca DP bir başlangıca ihtiyacımız var.
  • dp[7] = False -> e hiç bir kelime uymuyor.
  • dp[6] = False -> de hiç bir kelime uymuyor.
  • dp[5] = False -> ode hiç bir kelime uymuyor.
  • dp[4] = True -> code sözlükte var.
  • dp[3] = False -> tcode hiç bir kelime uymuyor.
  • dp[2] = False -> etcode hiç bir kelime uymuyor.
  • dp[1] = False -> eetcode hiç bir kelime uymuyor.
  • dp[0] = True -> leet sözlükte var.
  • Burada dp[0] = dp[0 + len(w)] şeklinde kontrol ederek bir desen yakalayabiliriz.
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True
        
        for i in range(len(s) -1, -1, -1):
            for w in wordDict:
                if (i + len(w)) <= len(s) and s[i : i +len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break
        return dp[0]