检查是否存在给定字符串的排列，该排列不包含任何单调子串

单调子串是指给定字符串的连续子串，其中字符的值全部严格递增或严格递减。单调子串是值严格递增或严格递减的字符串序列。

方法

  • 动态规划

  • 回溯法

方法 1：动态规划

一种技术是应用动态规划来构建子问题的表格，这里表格中的每个项目 (i, j) 表示是否存在字符串 S[i...j] 的排列，该排列不包含任何单调子串。当 i=j 时，子串仅包含一个字符，因此是微不足道的单调的。

语法

令 s 为长度为 n 的输入字符串，dp[k][i] 为布尔变量，如果 s 的前 k 个字符的排列以第 i 个字符结尾并且不包含任何单调子串，则返回 true。

  • 对于所有 1 ≤ i ≤ n，dp[1][i] 等于 true。

  • 如果 k > 1 且 i > j，则当且仅当 dp[k-1] [j] 为 true 且 s[i] 不在以索引 j 结尾的排列的最后两个字母生成的单调子串中时，dp[k][i] = true。

问题的解决方案为 true 当且仅当存在值 k 使得对于某些 1 ≤ i ≤ n，dp[k][i] 为 true。

算法

步骤 1 − 假设 S 是长度为 n 的输入字符串。

步骤 2 − 创建一个大小为 n x 2 的二维布尔数组 DP，这里 DP[i][0] 表示以位置 i 结尾的递减子序列的存在，而 DP[i][1] 表示以位置 i 结尾的递增序列的存在。

步骤 3 − 将 DP [0][0] 和 DP [0][1] 都设置为 false。

步骤 4 − 对从 1 到 n-1 的每个 i 执行以下操作 −

  • 如果存在 j 使得 0 ≤ j < i 且 S[j] > S[i] 并且 DP[j][1] 为 true，则将 DP[i][0] 设置为 true。

  • 如果存在 j 使得 0 ≤ j < i 且 S[j] ≤ S[i] 并且 DP[j][0] 为 true，则将 DP[i][1] 设置为 true。

步骤 5 − 确定是否存在点 i 使得 DP[i][0] 和 DP[i][1] 都为 true。如果发生这种情况，则返回 false，表示排列中存在单调子串。

步骤 6 − 否则，返回 true，因为输入字符串的任何排列中都不存在单调子串。

示例

为了开始我们对这个问题的方法，我们首先建立一个名为“dp”的二维 DP 矩阵。在此矩阵中，每个元素都表示形成长度为 i 的字符串所需的升序和降序字符。最初，为了正确设置我们矩阵以备将来使用，我们将单元格 [1] 内的两个元素的值都分配为“一”。向前填充后续单元格，我们的递归关系使用以下公式：“dp[i-1],[0]”用于计算“dp[[i],[0]]”，而“dp[[i-13,[01'+[j-11,[j41',[i]]”生成“dpi[l,[I],l”。但是，在使用此处提到的上下文中任何进一步的策略之前；在通过 [cnt] 计算给定字符串中特定字符出现的次数后，我们考虑是否存在重新排列的概念，从而导致小于或等于“dp[i][0]+dp[i][1]”的微小/大量子序列计数值。在评估后收到“true”验证了我们方法的合法性，而其他任何内容都可能被视为不令人满意的输出。

Open Compiler
#include <iostream>
#include <cstring>
using namespace std;

bool checkMonotonous(string s) {
   int n = s.length();
   int dp[n + 1][2];
   memset(dp, 0, sizeof(dp));
   dp[1][0] = dp[1][1] = 1;
   for (int i = 2; i <= n; i++) {
      dp[i][0] = dp[i - 1][1];
      dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
   }
   int cnt[26] = {0};
   for (int i = 0; i < n; i++) {
      cnt[s[i] - 'a']++;
   }
   for (int i = 1; i <= n; i++) {
      if (dp[i][0] + dp[i][1] > cnt[i - 1]) {
         return false;
      }
   }
   return true;
}

int main() {
   string s = "aabbcc";
   if (checkMonotonous(s)) {
      cout << "There exists a permutation of the given string which doesn't contain any monotonous substring.\n";
   } else {
      cout << "There does not exist permutation of given string which does not contain monotonous substring.\n";
   }
   return 0;
}

输出

There does not exist permutation of given string which does not contain monotonous substring.

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

方法 2：回溯法

回溯法也可用于生成字符串的所有可能排列，然后检查其中任何一个是否包含单调子串。由于排列数量对于大型字符串来说可能非常大，因此这种方法可能会延迟，但它保证如果存在解决方案则会找到解决方案。

语法

在 C++ 中使用回溯法解决检查字符串排列（不包含单调子串）问题的通用语法。

bool hasMonotonousSubstring(string s) {
   sort(s.begin(), s.end());
   do {
      bool valid = true;
   for (int i = 2; i < s.length(); i++) {
      if (s[i] == s[i-1] + 1 && s[i-1] == s[i-2] + 1) {
         valid = false;
         break;
      }
      else if (s[i] == s[i-1] - 1 && s[i-1] == s[i-2] - 1) {
         valid = false;
         break;
      }
   }
   if (valid) return true;
   } while (next_permutation(s.begin(), s.end()));
   return false;
}

算法

使用 C++ 中的回溯法生成不包含单调子串的给定字符串的排列的通用方法如下 −

步骤 1 − 生成提供的字符串的所有排列。

步骤 2 − 检查每个排列以查看它是否包含任何单调子串。如果不是，则该排列是有效的解决方案。

步骤 3 − 返回有效解决方案并在发现解决方案时结束过程。

步骤 4 − 如果您已生成所有可能的排列并且没有一个是有效的，则返回到上一步并尝试不同的候选解决方案。

示例 2

isMonotonous () 方法确定提供的字符串是否包含任何单调子串。它通过遍历文本并查找长度为 3 的严格递增或严格递减的子串来实现此目的。

permute () 函数通过回溯生成提供的字符串的所有排列。它将字符串 s、初始索引 l 和结束索引 r 作为输入。如果初始索引等于结束索引，则我们已生成排列。使用 isMonotonous () 方法，我们确定此排列是否包含任何单调子串。

main () 函数初始化输入字符串并将其按字典序升序排序。然后，它调用 permute () 函数，起始索引为 0，结束索引为字符串长度减 1。如果未找到任何无单调子串的排列，我们打印“未找到排列”。

Open Compiler
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isMonotonous(string s) {
   for (int i = 2; i < s.length(); i++) {
      if ((s[i] > s[i-1] && s[i-1] > s[i-2]) || (s[i] < s[i-1] && s[i-1] < s[i-2])) {
         return true; 
      }
   }
   return false; 
}
bool permute(string s, int l, int r) {
   if (l == r) {
      if (!isMonotonous(s)) {
         cout << s << endl;
         return true;
      }
   }
   else {
      for (int i = l; i <= r; i++) {
         swap(s[l], s[i]);
         if (permute(s, l+1, r)) {
            return true;
         }
         swap(s[l], s[i]);
      }
   }
   return false;
}
int main() {
   string s = "abc";
   sort(s.begin(), s.end()); // sort the string in lexicographically increasing order
   if (!permute(s, 0, s.length()-1)) {
      cout << "No permutation found" << endl;
   }
   return 0;
}

输出

acb

结论

总而言之，确定给定字符串是否具有不包含任何单调子串的排列是一项具有挑战性的任务，需要仔细的分析和算法设计。

一种可能的解决方案是生成字符串的所有可能排列，并检查每个排列中是否存在单调子串。但是，由于对于较大的输入大小，排列的数量可能非常大，因此这种方法效率低下。

更新于: 2023-07-31

214 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告