[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 828|回复: 0
收起左侧

[算法题] 求问一个leetcode上的时间复杂度问题

[复制链接] |试试Instant~ |关注本帖
leoyang 发表于 2014-4-24 15:26:00 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
本帖最后由 leoyang 于 2014-4-24 15:27 编辑

Leetcode上的Word Break 2 :http://oj.leetcode.com/problems/word-break-ii/

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].


这个问题我用两种方法解:

1.dp保存在0~k位置子串被分割的解集,k+1位置的就可以通过遍历0~k位置解集来获得。最后返回dp[n]

2.二维dp保存[i,j]是否可以通过i~j是解集中的一个单独子串,0~i-1是一个可能解集的方法分割,然后dfs遍历生成结果。

我表达的可能不太好,我把代码贴在最后面。方法2能AC,方法1超时,但是其实我理解的是dfs重复计算了一部分中间结果,比如2个不同的最终解集都包含了位置0~4(举例)子串的解集,那不就是重复计算了两边吗?而方法1只要用dp[4]就可以了。

总的来说我觉得方法1的时间复杂度是O(n^3),而dfs方法似乎是指数级别的(虽然用提前计算的dp剪枝掉一些,但是似乎没有影响渐进的时间复杂度)

用的是python,发代码的功能似乎不支持缩进所以就直接PO上来了。

方法1的代码:
class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a list of strings
    def wordBreak(self, s, dict):
        dp=[]
        f=[]
        for i in range(len(s)):
            ft=[]
            for j in range(i,len(s)):
                st=s[i:j+1]
                if st in dict:
                    ft.append(True)
                else:
                    ft.append(False)
            f.append(ft)
        for i in range(len(s)):
            arri=[]
            for j in range(i):
                s2=s[j+1:i+1]
                if f[j+1][i-j-1]:
                    tmp=""
                    dpj=dp[j]
                    for t in dpj:
                        tmp=t
                        tmp+=" "+s2
                        if len(tmp)>0:
                            arri.append(tmp)
            if f[0]:
                arri.append(s[:i+1])
            dp.append(arri)
        return dp[len(s)-1]

方法2的代码
class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a list of strings
    def wordBreak(self, s, dict):
        dp=[]
        f=[]
        self.fill(f,len(s),False)
        f.insert(0,True)
        for i in range(len(s)):
            l=[]
            self.fill(l, len(s), False)
            dp.append(l)
        for i in range(len(s)):
            for j in range(i,-1,-1):
                if f[j] and s[j:i+1] in dict:
                    f[i+1]=True
                    dp[j]=True
        ans=[]
        path=[]
        self.dfs(ans, path, len(s)-1, dp,s)
        return ans


    def dfs(self,ans,path,cur,dp,s):
        if cur==-1:
            w=""
            for i in range(len(path)):
                if i>0:
                    w=" "+w
                w=path+w
            ans.append(w)
            return
        for i in range(cur+1):
            if dp[cur]:
                path.append(s[i:cur+1])
                self.dfs(ans, path, i-1, dp, s)
                path.pop()


    def fill(self,l,n,c):
        for i in range(n):
            l.append(c)


本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-25 19:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表