在 O(n) 中查找字符串的所有循环排列

Question

鉴于问题：查找字符串的所有循环排列

例如：给定一个字符串：“abcd”

字符串的所有循环排列将是：“abcd”、“dabc”、“cdab”、“bcda”

这是我尝试过的：

for(int i = 0; i < str.size(); i++){
    permu.push_back(str);
    str.insert(0, 1, str[str.size()-1]);
    str.erase(str.end()-1);
}

由于插入和擦除函数需要 O(n) 使整体解决方案 O(n^2)

有没有办法在 O(n) 或更少的时间内解决这个问题？

Answer 1

你可以用string_viewO(n) 来做：

std::vector<std::string_view> get_perms(std::string& str) {
    auto orig_length = str.length();
    str += str;
    std::vector<std::string_view> ret;

    std::string_view sv{str};
    for (int i = 0; i < orig_length; i++) {
        auto sv2 = sv.substr(i, orig_length);
        ret.push_back(sv2);
    }
    return ret;
}

取 a 的子字符串string_view是常数时间，但您需要确保原始字符串string保持活动状态。这就是该函数str作为非常量引用的原因。