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

在这个问题中，我们将检查是否可以根据给定的条件，仅递增字符串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’的差值为27。
‘r’ -> ‘s’的差值为53。

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

方法1

此方法将计算字符串S和T相同索引处两个字符之间的循环差值。我们可以统计具有相同差值的字符数量。要将字符串S转换为T，K必须大于（差值 + 数字 * 26），因为我们只能执行一次增量’I’。

算法

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

步骤2 - 初始化’freq’列表以存储差值的频率。

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

步骤4 - 计算字符串的两个字符之间的循环差值。为了进行循环差值计算，将26加到差值上，然后将其与26取模。

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

步骤6 - 增加列表中差值的频率。

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

示例

#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;
}