[LeetCode] 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-emptywords, determine if s can be segmented into a space-separated sequence of one or more dictionary words.


Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.



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 "leetcode" can be segmented as "leet code".



Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: False


解題邏輯與實作

這題是要將題目給定的句子拆解成字典中的單字。第一個想到的就是我在最愛的暴力法,拆、拆、拆就對了!


遞迴

也就是暴力解,想法很簡單,就是把句子拆成前後兩句下去查,一旦有一種拆法可以查的到就回傳True,否則回傳False。當然為了避免大量重複計算,例外用HashTable紀錄查過得結果,解法如下:

  1. 查詢此單字是否存在於字典中
    1. 有,則回傳True
    2. 否,則向下執行
  2. 使用一個指標由前向後遍歷此單字,並依指標位置,將單字拆成前後部份並呼叫遞迴傳入,唯有當前後部份皆可在字典中查到時才回傳True,否則繼續向後遍歷。
  3. 若遍歷完整個字串皆無法找到拆解法則回傳False



程式碼

class Solution:
	def __init__(self, mydict=None):
		self.mydict = mydict
		self.memo = {}

	def set_dict(self,mydict):
		self.mydict = mydict
		
	def wordBreak(self, s, wordDict):
		self.set_dict(set(wordDict))
		return self.check(s)

	def check(self, s):
		length = len(s)
        
		if s in self.memo:
			return self.memo.get(s)

		if length <= 0 or s in self.mydict:
			self.memo[s] = True
			return True

		result = False
		for i in range(1, length):
			result = self.check(s[:i]) and self.check(s[i:])
			if result :
				break

		self.memo[s] = result
		return result

但果不期然,效率有點差跑出了個 740 ms, 1.20% 的成績,摸摸鼻子改寫DP去。


Dynamic Programming

這題大概是難得我這幾天整理的題目中,DP解終於不是欠著的題目了XDDD

這邊使用了一個dp陣列紀錄結果,其中dp[i]中紀錄著字串s[:i]是否能夠拆解,接下來若是s[i:j]也可以進行拆解,因為已知s[:i]可拆解,又s[i:j]可拆解,故s[:j]可拆解,因此紀錄dp[j]為True,按這關係推導,最後就可以判斷目標字串是否可以被拆解。



程式碼

class Solution:
	def wordBreak(self, s, wordDict):
		n = len(s)
		dp = [False] * (n + 1)
		dp[0] = True
	
		words = set(wordDict)
		for j in range(n):
			for i in range(j, -1, -1):
				if dp[i] and s[i:j + 1] in words:
					dp[j + 1] = True
					break
		return dp[n]

這效能果然好上不少,跑出了68 ms, 15.49% 的成績。


Dynamic Programming 改進版

看到我的code雖然有比上次進步,但其實無條件進位也才16%而已,有些好奇前面code是怎樣的,所以手賤點了前段班的code出來看。

發現他雖然也是用DP解,但他加上了點巧思,與我不同的是他是由後向前遍歷,並寫加上了檢查距離的限制,限制在字典中最長的單字長度上,檢查再多也沒有意義,因為字典就沒有這麼長的單字咩。最後跑出來成績為 36 ms, 99.65% 。



程式碼

class Solution:
	def wordBreak(self, s, wordDict):
		words = set(wordDict)
		maxLen = 0
		for word in wordDict:
			maxLen = max(maxLen, len(word))
		n = len(s) 
		dp =  [False] * (n + 1)
		dp[n] = True 

		for i in range(n - 1, -1, -1):
			for j in range(i + 1, min(i + maxLen, n) + 1): 
				if dp[j] and s[i:j] in words:
					dp[i] = True
					break 
		return dp[0]



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET