本帖最后由 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.
(string) chunk = "lololololo"
(string) word = "lol"
(string) chunk = "goodgooogoogfogoood"
(string) word = "goo"
我用python写了个 answer 函数，这个函数可以应对这样的问题，但是效率太低了，我实在不知道怎么样才能提高它的效率了。至于为什么超时就是我注解的那两行，一行是O(n)的复杂度，n代表加密后的字符串长度，另一行一行是递归调用，换句话说复杂度＝O(插入次数*n)。
def answer(chunk, word):
if len(chunk) < len(word):
indexs = 
for i in range(len(chunk)-len(word)+1):
if chunk[i:i+len(word)] == word:
ans = chunk
for i in indexs:
tmp = answer(chunk[:i]+chunk[i+len(word):],word)
if len(tmp) < len(ans) or len(tmp) == len(ans) and tmp < ans:
ans = tmp
- import uuid
- import random
- def answer(chunk, word):
- # your code here
- if len(chunk) < len(word):
- return chunk
- indexs = 
- for i in range(len(chunk)-len(word)+1):
- if chunk[i:i+len(word)] == word:
- ans = chunk
- for i in indexs:
- 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
- def my_random_string(string_length=10):
- """Returns a random string of length string_length."""
- rand = str(uuid.uuid4()) # Convert UUID format to a Python string.
- rand = rand.replace("-","") # Remove the UUID '-'.
- return rand[0:string_length] # Return the random string.
- while 1:
- orig_str = my_random_string(random.randrange(3,5))
- noise_str = my_random_string(random.randrange(2,21))
- if orig_str in noise_str or noise_str in orig_str:
- insert_num = random.randrange(2,5)
- output_str = orig_str
- for i in xrange(insert_num):
- rand_pos = random.randrange(0,len(output_str))
- output_str = output_str[:rand_pos]+noise_str+output_str[rand_pos:]
- if orig_str != answer(output_str, noise_str):
- print(output_str+" "+orig_str+","+noise_str)