[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1701|回复: 2
收起左侧

[字符串] Google Challenge重复删除字符串

[复制链接] |试试Instant~ |关注本帖
我的人缘0
qetu133 发表于 2016-5-17 03:16:30 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

x
本帖最后由 qetu133 于 2016-5-17 09:14 编辑

我遇到个题目,想了很久都不知道怎么做好点,这个题目就是直接匹配是绝对会超时的,不知道用什么样的方法才能解出来。Your spy, Beta Rabbit, has managed to infiltrate a lab of mad scientists who are turning rabbits into zombies. He sends a text transmission to you, but it is intercepted by a pirate, who jumbles the message by repeatedly inserting the same word into the text some number of times. At each step, he might have inserted the word anywhere, including at the beginning or end, or even into a copy of the word he inserted in a previous step. By offering the pirate a dubloon, you get him to tell you what that word was. A few bottles of rum later, he also tells you that the original text was the shortest possible string formed by repeated removals of that word, and that the text was actually the lexicographically earliest string from all the possible shortest candidates. Using this information, can you work out what message your spy originally sent?
If the final chunk of text was "lolol," and the inserted word was "lol," the shortest possible strings are "ol" (remove "lol" from the beginning) and "lo" (remove "lol" from the end). The original text therefore must have been "lo," the lexicographically earliest string.

Write a function called answer(chunk, word) that returns the shortest, lexicographically earliest string that can be formed by removing occurrences of word from chunk. Keep in mind that the occurrences may be nested, and that removing one occurrence might result in another. For example, removing "ab" from "aabb" results in another "ab" that was not originally present. Also keep in mind that your spy's original message might have been an empty string.

chunk and word will only consist of lowercase letters [a-z].
chunk will have no more than 20 characters.
word will have at least one character, and no more than the number of characters in chunk.

Test cases
==========

Inputs:
   (string) chunk = "lololololo"
   (string) word = "lol"
Output:
   (string) "looo"

Inputs:
   (string) chunk = "goodgooogoogfogoood"
   (string) word = "goo"
Output:
   (string) “dogfood"

我用python写了个 answer 函数,这个函数可以应对这样的问题,但是效率太低了,我实在不知道怎么样才能提高它的效率了。至于为什么超时就是我注解的那两行,一行是O(n)的复杂度,n代表加密后的字符串长度,另一行一行是递归调用,换句话说复杂度=O(插入次数*n)。
def answer(chunk, word):
   if len(chunk) < len(word):
       return chunk
   indexs = []
   #找到符合word的index保存(可以改成KMP算法,依然超时)
   for i in range(len(chunk)-len(word)+1):
       if chunk[i:i+len(word)] == word:
           indexs.append(i)
   ans = chunk
   for i in indexs:
        #逐个index查找最短的原始信息
       tmp = answer(chunk[:i]+chunk[i+len(word):],word)
       if len(tmp) < len(ans) or len(tmp) == len(ans) and tmp < ans:
           ans = tmp
   return ans

print(answer('6bb6b67b7b67b67bbc' ,'b67b'))
print(answer("lololololo","lol"))
print(answer('goodgooogoogfogoood','goo'))
print(answer('0d960750d960d9607500750d960750002a','0d960750'))
=================自动验证脚本==================================
  1. import uuid
  2. import random

  3. def answer(chunk, word):
  4.     # your code here
  5.     if len(chunk) < len(word):
  6.         return chunk
  7.     indexs = []
  8.     for i in range(len(chunk)-len(word)+1):
  9.         if chunk[i:i+len(word)] == word:
  10.             indexs.append(i)
  11.     ans = chunk
  12.     for i in indexs:
  13.         tmp = answer(chunk[:i]+chunk[i+len(word):],word)
  14.         if len(tmp) < len(ans) or len(tmp) == len(ans) and tmp < ans:
  15.             ans = tmp
  16.     return ans

  17. def my_random_string(string_length=10):
  18.     """Returns a random string of length string_length."""
  19.     rand = str(uuid.uuid4()) # Convert UUID format to a Python string.
  20.     rand = rand.replace("-","") # Remove the UUID '-'.
  21.     return rand[0:string_length] # Return the random string.

  22. while 1:
  23.     orig_str = my_random_string(random.randrange(3,5))
  24.     noise_str = my_random_string(random.randrange(2,21))
  25.     if orig_str in noise_str or noise_str in orig_str:
  26.         continue
  27.     insert_num = random.randrange(2,5)
  28.     output_str = orig_str
  29.     for i in xrange(insert_num):
  30.         rand_pos = random.randrange(0,len(output_str))
  31.         output_str = output_str[:rand_pos]+noise_str+output_str[rand_pos:]
  32.     if orig_str != answer(output_str, noise_str):
  33.         print(output_str+" "+orig_str+","+noise_str)
  34.         raw_input()
复制代码


上一篇:leetcode刷过的题目老是忘记解法
下一篇:求亚麻的面筋总结
我的人缘0
stellari 发表于 2016-5-17 06:21:44 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这题最重要的描述部分你没有贴全吧?
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
 楼主| qetu133 发表于 2016-5-17 08:13:35 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2016-5-17 06:21
这题最重要的描述部分你没有贴全吧?

这就是最重要的部分啦,就是递归删除子串呢。前面讲的是什么兔博士要解密什么的,然后原文信息被插入很多的杂信息,现在已知加入的pattern,然后寻找原来的最短的信息。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-19 11:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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