检查字符串是否可以通过插入与相邻字符相同的字符转换为另一个字符串

在这个问题中，我们将检查是否可以通过在给定字符串的任何两个相同字符之间插入相同的字符来将字符串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。

示例

Open Compiler
#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) 用于存储编码列表。

当我们需要解决任何基于给定字符串的连续字符频率的问题时，游程编码算法非常有用。

更新于：2023年7月17日

76 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告