資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學構成給定字串所需的字串字首和字尾的最小數量
字首是從給定字串的第零個索引開始，長度可以從1到字串大小的子字串。類似地，字尾是長度從1到字串大小，並在最後一個索引結束的子字串。我們將得到兩個字串，並必須透過以任何方式使用第二個字串的任意數量的字首和字尾來建立第一個字串。如果無法透過給定的方法從給定的字串建立給定字串，我們將返回-1。
示例
Input 1: string str1 = “tutorialspoint” string str2 = “pointstutorial”
Output: 2
解釋
我們可以使用字首“points”和字尾“tutorial”，並將它們連線起來得到第一個字串。這隻需要兩個子字串，這就是我們的答案或輸出。
Input 2: string str1 = “randomstring” string str2 = “anotherstring”
Output: -1
解釋
沒有辦法從給定第二個字串的字尾或字首中得到第一個字串。
方法
為了解決這個問題，我們將使用動態規劃的概念，即儲存已經發生的情況。
首先，我們將建立一個函式，該函式將兩個字串作為引數並返回一個整數。
在函式中，我們將首先獲取字串的長度，並建立一個雜湊集和一個臨時字串來獲取字首。
我們將遍歷第二個字串並獲取所有字首，並將它們儲存在雜湊集中。同樣，透過從後向前遍歷字串，我們可以獲取所有後綴並將它們儲存在雜湊集中。
然後，我們將建立一個數組來儲存動態規劃的結果，並在陣列的每個索引處儲存-1。
使用巢狀for迴圈，我們將第一個字串分成塊，並找到是否可以從雜湊對映中連線所有塊。
我們將嘗試減少所需的子字串數量，如果不可能，則返回-1。
示例
#include <bits/stdc++.h>
using namespace std;
// function to find the required number of substrings
int count(string str1, string str2){
unordered_set<string> st; // set to store the strings from the prefix and suffix
string temp = "";// string to store the prefixes and suffixes
int len1 = str1.size(); // size of the first string
int len2 = str2.size(); // getting size of the second
// getting prefixes of string second
for (int i = 0; i < len2; i++){
temp += str2[i]; // adding the characters to temporary string
st.insert(temp); // insert current string to set
}
// getting all the sufixes
for (int i = len2-1; i >= 0; i--){
temp = str2.substr(i); // getting suffixes
st.insert(temp); // adding suffixes to the set
}
// Initialize memo array to store the answer
int memo[len1+1];
memset(memo, -1, sizeof(memo)); // initializing array
memo[0] = 0;
// applying the concepts of dp
// traversing over the main string and will try to
// partition string into chunks
for (int i = 0; i < len1; i++){
for (int j = 1; j <= len1 - i; j++){
// check if the set contain current substring
if (st.find(str1.substr(i, j)) != st.end()){
if (memo[i] == -1){
continue;
}
if (memo[i + j] == -1){
memo[i + j] = memo[i] + 1;
}
else {
memo[i + j] = min(memo[i + j], memo[i] + 1);
}
}
}
}
// Return the answer
return memo[len1];
}
int main(){
string str1 = "tutorialpoints";
string str2 = "pointstutorial";
// calling function to find the minimum number of substrings required
cout <<"The minimum count of prefixes and suffixes of a string required to form given string is "<<count(str1, str2)<<endl;
return 0;
}
輸出
The minimum count of prefixes and suffixes of a string required to form given string is 2
時間和空間複雜度
上述程式碼的時間複雜度為O(N^2)，因為我們正在獲取所有後綴的複雜度為O(N^2)，但這可以透過反轉字串來減少。此外，我們將字串儲存到雜湊集中，使得時間複雜度為O(N^2)，而動態規劃的巢狀for迴圈也為O(N^2)。
上述程式碼的空間複雜度為O(N^2)，因為我們將所有後綴和字首儲存在雜湊對映中。
結論
在本教程中，我們實現了一個程式碼來查詢作為給定字串的字尾和字首的最小子字串數量，以建立另一個給定字串，如果不可能，我們列印-1。我們使用了動態規劃的概念，將元素儲存在雜湊集中，然後使用巢狀迴圈，時間和空間複雜度為O(N^2)。
285 次瀏覽
