檢查是否存在 2 * K + 1 個非空字串,其連線構成給定的字串
在這個問題中,我們給定一個字串,我們需要將字串分成 k + 1 個子字串,使得 k + 1 個子字串與其反轉的連線可以給出原始字串。
觀察可以解決問題。如果字串的前 k 個字元和後 k 個字元相同,我們可以說可以根據給定條件建立 k + 1 個字串。
問題陳述 – 我們給定一個長度為 N 的字串,包含小寫字母字元和正整數 K。我們需要找到是否可以找到總共 k + 1 個字串,使得字串 A1、A2、A3、…、Ak、A(k + 1) 及其反轉 AK、A(k-1)、…、A3、A2、A1 的連線是原始字串 s。
示例
輸入 – str = "tutorialsotut"; k = 4
輸出 – 是
解釋 – 我們可以建立總共 5 (4 + 1) 個字串,分別是 't'、'u'、't'、'o' 和 'rials',當我們根據給定條件連線它們時,我們可以得到原始字串。
輸入 – str = "ststs", k = 1
輸出 – 是
解釋 – 我們可以建立 's' 和 'tst' 共 2 個字串。
輸入– str = “spres”, k = 3
輸出– 否
解釋 – 我們無法建立總共 4 個字串,使其符合問題陳述中給出的條件。
方法 1
在這種方法中,我們將使用 for 迴圈來比較字串的前 k 個字元與後 k 個字元。如果字串的前 K 個字元等於後 k 個字元,我們可以說可以建立 K + 1 個字串,因此當我們將它們按實際順序和反向順序合併時,我們可以得到原始字串。
演算法
將字串的長度儲存在 'len' 變數中。
如果 2*k + 1 大於字串長度,則返回 false,因為無法透過按實際順序和反向順序合併 k + 1 個字串來獲得原始字串。
使用 for 迴圈遍歷前 k 個字元和後 k 個字元。
在迴圈中,比較 str[i] 和 str[len - i - 1] 字元。如果它們不相同,則返回 false。
如果 for 迴圈完成所有迭代而沒有執行 return 語句,則返回 true。
示例
#include <bits/stdc++.h> using namespace std; // function to check if we can make k+1 substrings to get the original string by concatenating strings according to the given conditions. bool findStrings(string str, int k) { // get the length of the string int len = str.size(); // If the length of the string is less than 2*k+1, return false if (2 * k + 1 > len) { return false; } // traverse the string to check whether the first k characters are equal to the reverse of the last k characters or not for (int i = 0; i < k; i++) { if (str[i] != str[len - i - 1]) { return false; } } // Return true if the first k characters are equal to the last k characters return true; } int main() { string str = "tutorialsotut"; int K = 4; if (findStrings(str, K)) { cout << "Yes, we can make k+1 substrings according to the given conditions."; } else { cout << "No, we can't make k+1 substrings according to the given conditions."; } return 0; }
輸出
Yes, we can make k+1 substrings according to the given conditions.
時間複雜度 – O(K),因為我們遍歷字串的前 K 個字元。
空間複雜度 – O(1),因為我們使用常量空間。
方法 2
此方法使用 substr() 方法從原始字串中獲取子字串。此外,我們將使用 reverse() 方法反轉子字串。
在這裡,我們將比較前 k 個字元和後 k 個字元的反轉。如果它們相等,我們可以說可以建立 k + 1 個子字串,以便在合併後,我們可以得到實際字串。
演算法
如果給定字串的長度大於 2*k + 1,則返回 false。
使用 substr() 方法並獲取從 [0, k] 索引開始的子字串,並將其儲存到 'first' 變數中。
再次使用 substr() 方法,獲取從 [len - k, len] 索引開始的子字串,並將其儲存到 'last' 變數中。
使用 reverse() 方法反轉最後一個字串。
返回 first == last 的布林值。
示例
#include <bits/stdc++.h> using namespace std; // function to check if we can make k+1 substrings so that we can get the original string by concatenating strings according to the given conditions. bool findStrings(string str, int k) { // get the length of the string int len = str.size(); // If the length of the string is less than 2*k+1, return false if (2 * k + 1 > len) { return false; } // Get the first k characters string first = str.substr(0, k); // Get the last k characters string last = str.substr(len - k, k); // Reverse the string reverse(last.begin(), last.end()); // Return true if both the strings are equal. Otherwise, return false return (first == last); } int main() { string str = "ststs"; int K = 1; if (findStrings(str, K)) { cout << "Yes, we can make k+1 substrings according to the given conditions."; } else { cout << "No, we can't make k+1 substrings according to the given conditions."; } return 0; }
輸出
Yes, we can make k+1 substrings according to the given conditions.
時間複雜度 – O(K),因為我們獲取子字串。
空間複雜度 – O(K),因為我們將長度為 K 的子字串儲存在 'first' 和 'last' 變數中。
我們學習了兩種不同的方法來解決問題。第一種方法比第二種方法更最佳化,因為它具有更低的空間複雜度和相同的時間複雜度。