在给定加密模式下，从给定的字符串中查找字符串

---

在这个问题中，我们需要使用给定的加密规则从加密字符串中找到原始字符串。如果我们以相反的顺序使用加密规则，我们可以得到原始字符串。

问题陈述 – 我们给定一个加密字符串。此外，我们还给定一个包含多个字符串的字符串数组。我们需要从数组中找到一个字符串，这样如果我们根据以下规则进行加密，就可以得到加密字符串。

加密规则

• 加密字符串应以一个正整数开头，表示原始字符串中大写字母的数量。

• 在正整数之后，字符串应包含原始字符串的后三个字符，并以相反的顺序排列。

• 最后，字符串应包含一个正整数，表示字符串中所有数字的总和。

示例

输入

str_array = {"ABXC237klg", "esre45Qewr3"}, enc_str = "4glk12"

输出

ABXC237klg

解释 – 让我们解密 enc_str 字符串。

• 4 – 字符串应包含 4 个大写字符。

• glk – 原始字符串的后三个字符，以相反的顺序排列。

• 12 – 所有字符串数字的总和（2 + 3 + 7 = 12）。

因此，输出字符串遵循所有加密规则。

输入

str_array = {"ABXC237klp", "esre45Qewr3"}, enc_str = "4glk12"

输出

-1

解释 – 数组不包含 enc_str 字符串的解密字符串。

输入

str_array = {"JK253Der", "P5Q32mnDer", "GHD23fgd4"}; enc_str = "3reD10";

输出

JK253Der

解释 – 如果我们加密 'JK253Der' 或“P5Q32mnDer”字符串，我们会得到“3reD10”加密字符串。因此，我们可以在输出中打印这两个字符串中的任何一个。

方法 1

此方法将对给定字符串使用加密规则。首先，我们将提取起始整数并检查字符串是否包含大写字符的总数。之后，我们将提取三个字符并检查数组字符串是否最后以相反的顺序包含所有三个字符。最后，我们将提取加密字符串的最后一个整数并检查它是否等于字符串中所有数字的总和。

算法

步骤 1 – 将 'p' 变量初始化为 0，并将 'q' 变量初始化为字符串长度 -1。

步骤 2 – 使用 while 循环，并增加 'p' 的值，直到我们在字符串中获取字母字符以找到起始整数。

步骤 3 – 再次使用 while 循环，并减少 'q' 的值，直到我们在字符串中获取字母字符以找到结束整数。

步骤 4 – 使用 substr() 方法使用 p 和 q 值获取正整数和结束整数字符串。此外，使用 stoi() 方法将字符串转换为数字并将其存储在 'initial' 和 'ending' 变量中。

步骤 5 – 使用 substr() 方法获取字符串的 3 个中间字符，并使用 reverse() 方法反转它们。

步骤 6 – 开始遍历字符串数组，并将 'upperCase' 和 'digitSum' 变量初始化为 0，以存储大写字符的总数和特定字符串的数字总和。

步骤 7 – 使用嵌套循环遍历字符串。使用 isUpper() 方法检查当前字符是否为大写。如果是，则将 'upperCase' 变量的值增加 1。

步骤 8 – 使用 isdigit() 方法检查当前字符是否为数字。如果是，则将数字值添加到 'digitSum' 变量中。

步骤 9 – 如果 'upperCase' 变量的值等于 'initial'，'digitSum' 等于 'ending'，并且字符串的后三个字符等于 'middle'，则返回字符串。

步骤 10 – 最后，如果我们没有找到任何字符串，则返回 '-1'。

示例

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

string getOriginalStr(vector<string> str_array, string enc_str) {
    // String size
    int len = enc_str.size();
    int p = 0, q = len - 1;
    // Getting the digit's last index from the start
    while (isdigit(enc_str[p]))
        p++;
    // Gettig the character's first index from the end
    while (isdigit(enc_str[q]))
        q--;
    // Get initial integer
    int initial = stoi(enc_str.substr(0, p));
    // Get the ending integer
    int ending = stoi(enc_str.substr(q + 1, len - q));
    // Get middle string
    string middle = enc_str.substr(p, 3);
    // Reverse the string
    reverse(middle.begin(), middle.end());
    // Traverse array of string
    for (auto temp_str : str_array) {
        int upperCase = 0, digitsSum = 0;
        // Traverse string
        for (int p = 0; p < temp_str.length(); p++) {
            // For uppercase character
            if (isupper(temp_str[p]))
                upperCase++;
            // Get the sum of the present digits
            if (isdigit(temp_str[p]))
                digitsSum += (temp_str[p] - '0');
        }
        // Check for all conditions
        if (upperCase == initial && digitsSum == ending && temp_str.substr(temp_str.length() - 3, 3) == middle)
            return temp_str;
    }
    return "-1";
}
int main() {
    vector<string> str_array = {"ABXC237klg", "esre45Qewr3"};
    string enc_str = "4glk12";
    cout << "The original string is - " << getOriginalStr(str_array, enc_str);
    return 0;
}

输出

The original string is - ABXC237klg

时间复杂度 – O(P*Q)，其中 P 是数组的长度，Q 是字符串的最大长度。

空间复杂度 – O(1)，因为我们使用常量空间。

每当我们需要解决类似的问题时，我们都应该检查遵循给定规则的字符串并将加密字符串作为输出生成。