在給定加密模式下，從給定的字串中查詢字串

---

在這個問題中，我們需要使用給定的加密規則從加密字串中找到原始字串。如果我們以相反的順序使用加密規則，我們可以得到原始字串。

問題陳述 – 我們給定一個加密字串。此外，我們還給定一個包含多個字串的字串陣列。我們需要從陣列中找到一個字串，這樣如果我們根據以下規則進行加密，就可以得到加密字串。

加密規則

• 加密字串應以一個正整數開頭，表示原始字串中大寫字母的數量。

• 在正整數之後，字串應包含原始字串的後三個字元，並以相反的順序排列。

• 最後，字串應包含一個正整數，表示字串中所有數字的總和。

示例

輸入

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)，因為我們使用常量空間。

每當我們需要解決類似的問題時，我們都應該檢查遵循給定規則的字串並將加密字串作為輸出生成。