檢查是否存在 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' 變數中。

我們學習了兩種不同的方法來解決問題。第一種方法比第二種方法更最佳化，因為它具有更低的空間複雜度和相同的時間複雜度。