检查是否可以通过反转任何子字符串使字符串按字典序变小

在C++中，我们有一个内置的reverse()函数，用于反转子字符串以检查字符串是否可以按字典序变小。字典序是指按字典顺序对单词的字符进行排序。

让我们以一个字符串为例，来检查是否按字典序变小。

  • 我们将比较这两个单词以检查按字典序较小的单词，并取两个字符串，即“apple”和“army”。这两个字符串的第一个字母都是“a”。当我们移动到检查两个字母的第二个字符时，“p”在字母顺序上位于“r”之前。因此，apple按字典序小于army。

  • 在字符串“tutorialspoint”中，反转子字符串“oria”得到“airo”，它按字典序较小。然后最终字符串写成“tutairolspoint”。

  • 在字符串“tutorix”中，反转子字符串“tori”得到“irot”，它按字典序较小，因为第一个子字符串的开头是't'，第二个子字符串是'i'。然后'i'在字母顺序上位于't'之前，因此它使'irot'按字典序小于'tori'。然后最终字符串写成“tuirotx”

我们再举一个字符串的例子，例如“acwz”。

语法

reverse( str_name.begin(), str_name.end() )

解释

reverse函数是C++标准库的一部分，它接受两个参数“str_name.begin()”和“str_name.end()”。

  • str_name是用户建议的字符串名称。

  • begin()和end()是在reverse函数中使用的预定义内置函数。begin函数的作用是返回一个指向输入字符串第一个字符的迭代器。end函数的作用是返回一个指向输入字符串最后一个字符之前一个位置的迭代器。

请注意，reverse函数不返回任何值，因为它会就地修改容器（str_name）。

算法

  • 首先，我们将使用三个必要的头文件，即iostream、string和include<algorithm>，并声明std命名空间。

  • 我们将从main函数开始程序，在其中声明一个名为'str'的字符串变量，并在其中存储字符串'tutorialspoint'。然后，我们将声明布尔变量'isReverse'为'false'，以指示给定字符串未反转且处于原始形式。

  • 然后，我们将创建两个嵌套的for循环来检查'str'的每个可能的子字符串。然后将子字符串存储在名为'temp'的临时字符串中。

  • 之后，我们调用'reverse()'函数来反转存储在'temp'变量中索引'i'和'j'之间的子字符串。

  • 稍后创建一个if语句，通过比较变量'temp'和'str'来检查反转后的字符串是否按字典序较小。

  • 编译器将比较变量temp和str。如果两者相等，则变量'isReverse'将设置为true，并将中断if语句。

  • 现在，我们将检查isReverse的值，如果为true，它将打印if条件的语句，否则打印else条件的语句。

  • 退出程序。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

在这个程序中，我们将了解如何通过反转任何子字符串使字符串按字典序变小。

Open Compiler
#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;
int main() {
   string str = "tutorialspoint";
   // User can change this to test other strings such as acwz, groffer, etc
   bool isReverse = false; // it is used to indicate whether or not a substring has been found in the original string “str”.


   // use the loop through all possible substrings of str
   for (int i = 0; i < str.length(); i++) {
      for (int j = i+1; j < str.length(); j++) {
         string temp = str; 
         // create new temporary variable to store the value of str.
         // reverse the substring of i and j
         reverse ( temp.begin() + i, temp.begin() + j + 1 ); 
         // reverse function follow the header file name as <algorithm>
         if (temp < str) { 
            // Check whether the reversed string is lexicographically smaller
            isReverse = true;
            break;
         }
      }
   }
   if ( isReverse ) {
      cout << "Yes, this is lexicographically smaller by reversing a  substring." << endl;
   } else {
      cout << "No, this is not lexicographically smaller by reversing a substring." << endl;
   }
   return 0;
}

输出

如果我们输入值“tutorialspoint”，我们将得到以下结果：

Yes, this is lexicographically smaller by reversing a  substring.

如果我们输入值“acwz”，我们将得到以下结果：

No, this is not lexicographically smaller by reversing a substring.

结论

我们看到了如何使用字符串变量来计算通过反转任何子字符串按字典序较小的字符串。然后我们将字符串变量设置为临时变量。然后我们使用预定义函数“reverse()”来反向计算字典序单词。接下来，我们通过比较变量temp和str来检查按字典序较小的字符串并得到结果。

更新于：2023年4月20日

590 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告