算法：将字符串最优地分成三个子字符串

Question

最近我一直试图理解这个看似非常简单的问题。给定一个字符串 k，我们必须找到将该字符串 k 拆分为正好 3 个子字符串 k1、k2、k3 的最佳方法，使得 k1 + k2 + k3 = k。只有当通过反转每个子字符串并将它们重新连接起来后得到字典序最小的结果时，拆分才是最优的。

例如，取一个字符串 k="anakonda"。最佳拆分方式是 k1="a"，k2="na"，k3="konda"，因为在反转后 (k1="a", k2="an", k3="adnok")，我们得到 k1 + k2 + k3 = "aanadnok"，这是可能的字典序最小结果。

我的第一个方法是总是在下一个字典序最小字符处结束一个子字符串。

std::string str = "anakonda"

int first = find_min(str, 0, str.size() - 3); // Need to have at least 3 substrings so cannot search to the end
std::reverse(str.begin(), str.begin() + first + 1);

...

然而，这种方法有缺陷，因为对于给定的字符串 k = "ggggffffa"，该算法将无法工作。 我不知道如何正确解决这个问题。因此，我请求一个理论上的解决方案，以便我可以尝试自己实现它。

- emufan4568

---

如果有帮助的话，这只是围绕三向划分的描述所包含的大量额外信息。毕竟，字符串只是字符数组。 - Putnam

问题总是保证有解，因此k1、k2、k3>=1且不能为空。 - emufan4568

它是 fffggggfa 吗？ - nice_dev

是的，它是“fffggggfa”。 - emufan4568

好的，如果您不介意的话，能否分享一下问题的链接？ - nice_dev

Answer 1

这个算法可以解决问题，但可能需要优化：

#include <iostream>
#include <string>

std::string foo(std::string* ss) 
{ 
    std::string res;
    for (int i = 0; i < 3; i++)
        for (int j = ss[i].size()-1; j >= 0; j--) 
        res.push_back(ss[i][j]);
    return res;
}

int main()
{
  std::string s = "ggggffffa";
  std::string res = "";
  for (unsigned int i = 1; i < s.size() - 1; i++)
    for (unsigned int j = 0; j < i; j++)
    {
        std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
        std::string r = foo(ss);
        if (r < res || res == "") res = r;
    }
    std::cout << res << std::endl;  
}

描述：

1. 我们通过两个迭代器（第一个迭代器从第一个元素到字符串结尾，第二个迭代器从零元素到第一个迭代器）来确定所有可能的字符串分割索引。

for (unsigned int i = 1; i < s.size() - 1; i++)
    for (unsigned int j = 0; j < i; j++)

在索引i和j处分割字符串，并将三个子字符串写入字符串数组中；

std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};

3. 调用函数foo，该函数反转每个子字符串，将三个部分连接起来并返回结果字符串。
4. 检查从foo返回的结果字符串是否按字典顺序最小，如果是，则将一个新字符串赋值给结果。

if (r < res || res == "") res = r;

- Aleksey Kuchkin

---

@גלעד ברקן 编辑后，输出变得正确了。对于输入：“bndakonda”，输出应该是“adnbdnoka”。 - Aleksey Kuchkin