题目
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 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.
题意
给定一个非空的字符串s，和一个字典字符数组，判断该s字符串进行分割之后，分割的字符是否在字典中；字典中字符不重复，但是可以多次使用
例子
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
思路
先将字典中的字符存入map中，然后从第一个字符开始匹配，匹配失败就取下一个字符组成新的单词再进行匹配，匹配成功之后从如果不为最后一个，则取下一个组成新的字符串，在进行匹配；在前面有匹配成功的情况下，如果匹配失败了，说明当前的分隔是错误的，需要回到上一次匹配成功的地方，不进行分割，接着组成新的字符串进行匹配；
使用递归的方法很快可以实现如下代码：
var Slen int
var DictMap map[string]int
func wordBreak(s string, wordDict []string) bool {
if len(s)==0{
return false
}
Slen = len(s)
if len(wordDict)==0{
return false
}
DictMap = make(map[string]int)
for _,v := range wordDict{
DictMap[v]=1
}
return Segmentation(s,0)
}
func Segmentation(s string,index int) bool{
if index==Slen{
return true
}
temps := ""
for index<Slen{
temps+=string(s[index])
if _,ok := DictMap[temps];!ok{
index++
continue
}
index++
if Segmentation(s,index){
return true
}
}
return false
}
但是这样会TL,仔细观察一下代码,会发现在递归的过程中会进行很多次重复的计算（如遍历到某个位置t时，发现以该位置为start的分隔往后都不匹配，那么会回溯到上一次成功的地方，在上一次成功的地方往后寻找，期间成功匹配之后，又进入到以t为start的情况，那么就会再一次计算，可以保持以start为起始的分隔情况），所以可以保存之前的计算结果，提高速率；
对以上代码进行更改如下：
var Slen int
var DictMap map[string]int
var Memo map[int]int //记忆数组
func wordBreak(s string, wordDict []string) bool {
if len(s)==0{
return false
}
Slen = len(s)
if len(wordDict)==0{
return false
}
DictMap = make(map[string]int)
Memo = make(map[int]int)
for i,_:=range s{
Memo[i] = -1//初始为-1
}
for _,v := range wordDict{
DictMap[v]=1
}
return Segmentation(s,0)
}
func Segmentation(s string,index int) bool{
if index==Slen{
return true
}
if Memo[index]==1{//如果为1，说明,以当前位置为头的分隔情况为true,直接返回
return true
}
if Memo[index]==0{//如果为0，说明,以当前位置为头的分隔情况为false，直接返回
return false
}
temps := ""
start := index
for index<Slen{
temps+=string(s[index])
if _,ok := DictMap[temps];!ok{
index++
continue
}
index++
if Segmentation(s,index){
Memo[start] = 1 //记录当前结果
return true
}
}
Memo[start] = 0//记录当前结果
return false
}
总结
基本就是动态规划（dp）的题目了，可以通过以前的计算结果来减少重复计算，来找到最终的结果。本题关键点：记忆数组。
