是字符串字符串列表的排列

-1

給出了一個單詞列表，並給出了一個更大的字符串，我們如何找到該字符串是否是較小字符串的置換。是字符串字符串列表的排列

EG-s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE

EG-s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE

較小的話本身並不需要進行置換。現在的問題是，我們是否能找到小串的排序，例如，如果級聯的順序它提供了較大的字符串

下一個約束 - 從dict[]一些話也可以留下未使用的

下面給出複雜性O（n2）。任何其他方式來做到這一點......以提高複雜度或提高總體效率？大部分在Java中。提前致謝！

bool strPermuteFrom(unordered_set<string> &dict, string &str, int pos) 
{ 
    if(pos >= str.size()) 

    return true; 

    if(dict.size() == 0) 
    return false; 

    for(int j = pos; j < str.size(); j++){ 
    string w = str.substr(pos, j - pos + 1); 
    if(dict.find(w) != dict.end()){ 
     dict.erase(w); 
     int status = strPermuteFrom(dict, str, j+1); 
     dict.insert(w); 
     if(status){ 
     if(pos > 0) str.insert(pos, " "); 
     return status; 
     } 
    } 
    } 

    return false; 
} 


bool strPermute(unordered_set<string> &dict, string &str) 
{ 
    return strPermuteFrom(dict, str, 0); 
}

來源

2016-11-18 user7169931

爲您修復了標籤，將來請注意您使用的標籤 – 2016-11-18 16:24:20

@RC。我在這個問題中閱讀了「大部分以Java編程」，因此C++代碼可能只是錯誤語言現有解決方案的一個例子。最好讓用戶澄清而不是切換標籤。 – grek40

也許可能不是，目前這裏沒有Java，如果問題是如何將此代碼轉換爲更優化的Java版本，那麼它可能太寬了 – 2016-11-18 16:33:18

你給不採取unordered_set（相當於Java的HashSet的屬性）太大優勢的代碼示例;每個查找是O(1)，但它必須執行許多查找（對於每個可能的前綴，對於整個字符串的長度）。訂購的std::set（Java TreeSet）將允許您在單個O(log n)查找中查找給定點處的所有可能的前綴（隨後從該點開始掃描，直到您不再處理可能的前綴），而不是stringlengthO(1)在每個遞歸步驟查找。

那麼這段代碼在做什麼O(stringlength * dictsize^2)工作，使用排序集結構應該把它減少到O(dictsize log dictsize)的工作。字符串長度並不重要，因爲您不再查找前綴;您在每個遞歸步驟查找剩餘的字符串一次，並且因爲它是有序的，匹配的前綴將在整個字符串之前排序，不需要檢查單個子字符串。從技術上講，回溯仍然是必要的（以處理字典中的單詞是字典中的另一個單詞的前綴，例如act和acting），但除此之外，您不需要回溯;每次遞歸步驟只會有一次點擊，因此您只需執行dictsize查找，每個查找的成本爲log dictsize。

來源

2016-11-18 16:46:54 ShadowRanger

是字符串字符串列表的排列

回答

相關問題