檢查字串 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。

示例

#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。程式設計師還使用對映來儲存差異的頻率。