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

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

更新於: 2023年8月18日

63 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告