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

-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

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

回答

相关问题