需要減少我的程序的運行時間

我有一個問題，我必須找到一個字符串的連續子字符串，條件是子字符串的第一個和最後一個字母必須是相同的。我試過這樣做，但運行時間超過了幾個測試用例的問題的時間限制。我嘗試使用map for for循環，但我不知道如何爲嵌套for循環做。任何人都可以請幫我減少這個程序的運行時間？需要減少我的程序的運行時間

n = int(raw_input()) 
string = str(raw_input()) 
def get_substrings(string): 
    length = len(string) 
    list = [] 
    for i in range(length): 
    for j in range(i,length): 
     list.append(string[i:j + 1]) 
    return list 
substrings = get_substrings(string) 
contiguous = filter(lambda x: (x[0] == x[len(x) - 1]), substrings) 
print len(contiguous)

來源

2015-06-21 therealdev

如果我理解正確的問題，請讓我知道，如果那不是如此，但試試這個：

不知道這是否會加速運行，但我相信，這種算法可能對長字符串特別（消除嵌套循環）。遍歷字符串一次，用恆定時間查找（hashmap或數組，如果設置正確）將每個字符的索引（位置）存儲在數據結構中。完成後，您應該擁有一個存儲每個角色所有不同位置的數據結構。使用這個你可以很容易地檢索到子字符串。

例子：

codingisfun

採取字母i例如，在做什麼，我上面說的之後，你看看它的HashMap和看到，它發生在指數3和6。這意味着你可以做一些像substring（3，6）來獲得它。

不是最好的代碼，但它似乎是合理的起點......你也許能消除一些創造性思維的循環：

import string 
import itertools 

my_string = 'helloilovetocode' 

mappings = dict() 

for index, char in enumerate(my_string): 
    if not mappings.has_key(char): 
     mappings[char] = list() 

    mappings[char].append(index) 
    print char 

for char in mappings: 
    if len(mappings[char]) > 1: 
     for subset in itertools.combinations(mappings[char], 2): 
      print my_string[subset[0]:(subset[1]+1)]

來源

2015-06-21 04:36:26 soliman

謝謝你的幫助。你能舉個例子嗎？我是python新手，完全理解hashmaps。 – therealdev

字符串中的單個字母怎麼樣？他們不是子網嗎？這種方法是否可以用來打印單個字母，也就是子字符串？ – therealdev

這是一個簡單的修改，在第一個for循環打印每個字符後，將它們添加到字典映射 – soliman

的問題是，你的代碼遠遠效率太低算法複雜性的條款。

這裏有一個替代（索利曼的清潔劑，但稍慢版的我相信）

import collections 
def index_str(s): 
    """ 
    returns the indices characters show up at 
    """ 
    indices = collections.defaultdict(list) 
    for index, char in enumerate(s): 
     indices[char].append(index) 
    return indices 

def get_substrings(s): 
    indices = index_str(s) 
    for key, index_lst in indices.items(): 
     num_indices = len(index_lst) 
     for i in range(num_indices): 
      for j in range(i, num_indices): 
       yield s[index_lst[i]: index_lst[j] + 1]

與您的解決方案的算法問題是，你一味地檢查每一個可能的子串，當你可以很容易地確定哪些實際對是在一個單一的線性時間傳遞中。如果你只想要計數，那麼可以在O（MN）時間內容易地確定一個長度爲N和M的唯一字符串（給定一個字符的出現次數，你可以用數學方法計算出有多少個子字符串）。當然，在最壞的情況下（所有的字符都是相同的），你的代碼將和我們的代碼具有相同的複雜度，但是由於你有一個嵌套的for循環（n^2時間），所以你的代碼的平均複雜程度要差很多

來源

2015-06-21 08:14:42

需要減少我的程序的運行時間

回答

相關問題