问个算法题目

给一个字符串(无空格),一个字典,如果可以用字典单词分割字符串,就返回结果,返回任意一种结果即可,如果不存在,就返回空

例 字符串 “todayisaniceday”
字典 ["to","day","today","i","is","a","nice","day"]
返回 ["to day is a nice day"]

我用深度优先遍历,递归去做,但遇到点问题,有没有更好的算法呢?

全部评论
leetcode 原题
点赞 回复 分享
发布于 2016-09-15 09:47
深度优先遍历效率很低,想想如果字符串长度为100。这道题可以用动态规划,当然应该还有其他方法,我先给出状态转移方程式吧: dp[i]=true, 如果存在j<i,使得dp[j]=true并且 str.substr(j+1,i)属于字典;否则dp[i]=false。其中dp[i]表示str.sub(0,i)是否能被字典分割。该算法时间复杂度是O(n*n),还可以进行一些优化!
点赞 回复 分享
发布于 2016-09-15 09:57

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务