字典序最小字符串旋转

Z时代
2024-01-10
分类：综合

让我们考虑给定一个字符串，我们知道该字符串是一个字符序列。词典旋转是字符串的旋转，按词典顺序转换字符。

解决方案很简单，我们简单地将给定的字符串与其自身连接起来，然后在另一个数组中，存储字符串的所有旋转。之后按升序对数组进行排序，最小值为最终结果。

输入和输出

Input:

The String “BCAAFAABCD”

Output:

旋转字符串： “AABCDBCAAF”

算法

minStrRotation(str)

输入 -给定的字符串。

输出 - 所需的最小字符串旋转。

Begin
   n := length of str
   define strArr to store all rotations
   tempStr := concatenate str with str again
   for i := 0 to n, do
      strArr[i] := substring of tempStr from (i to n)
   done
   sort the strArr
   return strArr[0]
End

示例

#include <iostream>
#include <algorithm>
using namespace std;
string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];    //存储 str 的所有旋转的数组
   string tempStr = str + str;    //将 str 连接两次
   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);    //获取从第 i 个索引到第 n 个索引的子字符串
   sort(strArray, strArray+n);
   return strArray[0];    //第一个索引是结果
}
int main() {
   string str;
   cout << "输入字符串： "; cin >> str;
   cout << "旋转字符串： " << minStrRotation(str);
}