檢查字串是否可以透過插入與相鄰字元相同的字元轉換為另一個字串

---

在這個問題中，我們將檢查是否可以透過在給定字串的任何兩個相同字元之間插入相同的字元來將字串alpha1轉換為alpha2。

我們將使用遊程編碼演算法來解決這個問題，該演算法計算連續字元的頻率。

問題陳述 - 我們得到了兩個名為alpha1和alpha2的字串。我們需要檢查是否可以透過執行無限次以下操作來將字串alpha1轉換為alpha2。

• 選擇任何索引，並且當前索引和前一個索引處的字元相同，在它們之間插入相同的字元。

示例

輸入

alpha1 = "pqqrrs"; alpha2 = "pqqqqrrrs";

輸出

Yes

解釋 - 我們可以在第1個和第2個（基於0的索引）索引之間插入兩個'q'。此外，我們可以在第3個和第4個索引之間插入1個'r'，以使alpha1和alpha2字串相同。

輸入

alpha1 = "mnno"; alpha2 = "mnnol";

輸出

No

解釋 - 我們不能在alpha1字串中插入'l'，因為alpha1字串中不存在兩個相鄰的'l'。

輸入

alpha1 = "bcvfgdfgd"; alpha2 = "mnnol";

輸出

No

解釋 - alpha2的長度小於alpha1字串的長度。因此，我們不能透過插入字元將alpha1轉換為alpha2字串。

方法1

我們將使用遊程編碼演算法。它遍歷字串並計算連續字元的頻率。

對於字串alpha1 = "pqqrrs"和alpha2 = "pqqqqrrrs"，我們使用遊程編碼演算法得到以下輸出。

Run1 = {('p', 1), ('q', 2), ('r', 2), ('s', 1)}

Run2 = {('p', 1), ('q', 4), ('r', 2), ('s', 1)}

如果我們將其概括，我們可以看到以下結果。

Run1 = { (p1, m1), (p2, m2), (p3, m3) …. (pX, mX) }

Run2 = { (q1, n1), (q2, n2), (q3, n3) …. (qY, qY) }

如果Run1和Run2遵循以下條件，我們可以將alpha1轉換為alpha2。

• X == Y，表示相同數量的連續字元。

• p1 == q1, p2 == q2, … pX == qY，表示相同的字元。

• 它應該遵循mi == ni或mi < ni且mi > 1，因為只有當連續字元的頻率大於2時，我們才能插入字元。

演算法

步驟1 - 建立列表list1和list2來儲存字元和整數對。

步驟2 - 執行encodeStrings()函式對字串進行編碼並將輸出儲存在list1和list2中。

步驟2.1 - 在encodeStrings()函式中，將'cnt'初始化為1以儲存當前連續字元的計數。

步驟2.2 - 從第二個字元遍歷字串。

步驟2.3 - 如果當前字元與前一個字元不同，則將字元和'cnt'對插入列表中並將'cnt'重新初始化為0。

步驟2.4 - 將'cnt'加1。

步驟2.5 - 迴圈迭代完成後，將最後一個字元及其'cnt'值插入列表中。

步驟3 - 如果編碼列表的大小不同，則返回false。

步驟4 - 開始遍歷兩個列表。如果相同索引處的字元不同，則返回false。

步驟5 - 如果當前索引處字元的頻率值不同，則返回false。

步驟6 - 如果list1中的頻率值不小於list2或小於2，則返回false。

步驟7 - 最後，從函式返回true。

示例

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

void encodeStrings(string alpha, vector<pair<char, int>> &list) {
    int cnt = 1;
    for (int p = 1; p < alpha.length(); p++) {
        // When we find adjacent different characters
        if (alpha[p] != alpha[p - 1]) {
            list.push_back({alpha[p - 1], cnt});
            cnt = 0;
        }
        cnt++;
    }
    list.push_back({alpha.back(), cnt});
}
bool ConvertStrings(string alpha1, string alpha2) {
    vector<pair<char, int>> list1, list2;
    encodeStrings(alpha1, list1);
    encodeStrings(alpha2, list2);
    // If size of lists are not same
    if (list1.size() != list2.size()) {
        return false;
    }
    for (int p = 0; p < list1.size(); p++) {
        // Validate second condition
        if (list1[p].first != list2[p].first) {
            return false;
        }
        // Validate third condition
        if (!(list1[p].second == list2[p].second || (list1[p].second < list2[p].second && list1[p].second >= 2))) {
            return false;
        }
    }
    return true;
}
int main() {
    string alpha1 = "pqqrrs";
    string alpha2 = "pqqqqrrrs";
    bool res = ConvertStrings(alpha1, alpha2);
    if (res) {
        cout << "YES, It is possible to convert string alpha1 to alpha2." << endl;
    } else {
        cout << "NO, It is not possible to convert string alpha1 to alpha2." << endl;
    }
}

輸出

YES, It is possible to convert string alpha1 to alpha2.

時間複雜度 - O(P + Q)，其中P是alpha1的長度，Q是alpha2的長度。

空間複雜度 - O(M + N) 用於儲存編碼列表。

當我們需要解決任何基於給定字串的連續字元頻率的問題時，遊程編碼演算法非常有用。