讨论/《算法面试题汇总》 - 单词拆分 II/
《算法面试题汇总》 - 单词拆分 II
共 3 个回复

pen pineapple apple pen

4

考虑到需要给出具体结果,这时候动态规划就不好用了,可以考虑使用单词拆分中的dfs算法(虽然该算法在单词拆分中会超时)

 func wordBreak(s string, wordDict []string) []string {
     length := len(s)
     if length == 0 {
         return []string{""}
     }
     res := make([]string, 0)
     for i := 1; i <= length; i++ {
         if inDict(s[0:i], wordDict) {
             res0 := wordBreak(s[i:], wordDict)
             for j := 0; j < len(res0); j++ {
                 if res0[j]==""{
                     res = append(res, s[0:i]+res0[j])
                 }else {
                     res = append(res, s[0:i]+" "+res0[j])
                 }
             }
         }
     }
     return res
 }

 func inDict(s string, wordDict []string) bool {
     size := len(wordDict)
     for i := 0; i < size; i++ {
         if s == wordDict[i] {
             return true
         }
     }
     return false
 }`

我的结果与用例的结果不同
只能排序,排序规则是如果单词数量更多就排在前面,如果单词数量相同,第一个单词长度更长,排在前面