检查字符串 S 是否可以通过递增字符转换为 T

在这个问题中，我们将检查是否可以仅根据给定条件递增 S 的字符来将字符串 S 转换为 T。

在这里，我们只能将任何字符递增 'I' 一次。因此，如果我们需要将任何其他字符递增 'I' 次，则 K 的值应大于 26 + I。

问题陈述 – 我们给定一个字符串 S、T 和正整数 K。我们需要按照以下规则将字符串 S 转换为 T。

  • 我们可以取任何字符串字符并仅递增一次。

  • 我们可以取任何 I，其中 1 <= I <= K 仅一次来将特定字符递增 'I'。

  • 增量是循环的。因此，'z' 变为 'a'。

示例

输入

S = "abcde", T = "bdgik"; K = 7;

输出

Yes

解释

  • 要将 'a' 转换为 'b'，我们需要 1 个增量。

  • 要将 'b' 转换为 'd'，我们需要 2 个增量。

  • 要将 'c' 转换为 'g'，我们需要 4 个增量。

  • 要将 'd' 转换为 'I'，我们需要 5 个增量。

  • 要将 'e' 转换为 'k'，我们需要 6 个增量。

这里，所有增量数字仅使用一次且小于 K。因此，可以将字符串 S 转换为 T。

输入

S = "pqr", T = "qrs"; K = 1;

输出

No

解释

  • 我们可以将 'p' 递增 1 以转换为 'q'。

  • 同样，我们需要 1 个增量才能将 'q' 转换为 'r'，但我们已经使用了 1 个增量。因此，我们需要 1 + 26 = 27 个增量才能将 'q' 转换为 'r'。这里，27 大于 K，因此无法将字符串 S 转换为 T。

输入

S = "pqr", T = "qrs"; K = 56;

输出

Yes

解释

  • 'p' -> 'q' == 1 个增量。

  • 'q' -> 'r' == 1 + 26 = 27 个增量。

  • 'r' -> 's' == 1 + 26 + 26 = 53 个增量。

所有增量都小于 K。因此，我们可以将字符串 S 转换为 T。

方法 1

此方法将获取字符串 S 和 T 中相同索引处的两个字符之间的循环差。我们可以计算具有相同差异的字符的数量。K 应该大于 (差异 + 数字 * 26) 以将字符串 S 转换为 T，因为我们只能执行一次增量 'I'。

算法

步骤 1 – 如果两个字符串的大小不同，则返回 false。

步骤 2 – 初始化 'freq' 列表以存储差异的频率。

步骤 3 – 开始遍历字符串。

步骤 4 – 获取字符串两个字符之间的循环差。要获取循环差，请将 26 添加到差值并将其模数取 26。

步骤 5 – 如果差异为 0，则字符相同。如果差异不为 0，并且 diff + freq[diff] * 26 > K 为真，则返回 false。

步骤 6 – 在列表中递增差异的频率。

步骤 7 – 如果循环完成所有迭代，则返回 true。

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;

bool CanSToT(string S, string T, int K) {
   // Compare sizes
   if (S.size() != T.size())
      return false;
   // To store the frequency of characters
   vector<int> freq(26, 0);
   // Traverse string S
   for (int p = 0; p < S.size(); p++) {
      // Calculating the  required increment
      int diff = (T[p] - S[p] + 26) % 26;
      // To increment freq[diff] characters, we need minimum diff + freq[diff]*26 operations
      if (diff != 0 && diff + freq[diff] * 26 > K)
         return false;
      // Update character frequency
      freq[diff]++;
   }
   // Final answer
   return true;
}
int main() {
   string S = "abcde", T = "bdgik";
   int K = 7;
   if (CanSToT(S, T, K))
      cout << "Yes, it is possible to convert S to T.";
   else
      cout << "No, it is not possible to convert S to T.";
   return 0;
}

输出

Yes, it is possible to convert S to T.

时间复杂度 – O(N)，其中 N 是字符串大小。

空间复杂度 – O(1)，因为我们使用常量大小的列表来存储差异的频率。

我们学习了通过执行唯一增量来将字符串 S 转换为 T。程序员还使用映射来存储差异的频率。

更新于: 2023年8月29日

97 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告