有人可以幫我解決這個問題嗎？
使字串 A 等于字串 b 所需的最小切片數是多少？
例子：
String A = "gamergirls"
String B = "merils"
嘎| 梅爾| 克| 我| r | ls -> 5 片來制作 merils。
約束：
- 兩個字串中的字符都是小寫的。
- A.length && B.length <= 10^5
uj5u.com熱心網友回復：
我知道這個問題需要用 Java 解決，但我想用 C 提供解決方案。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int maximumSize=10;
vector<int> visitedStringA(maximumSize, 0);
vector<int> visitedStringB(maximumSize, 0);
vector<int> marked(maximumSize, 0);
void showContentVector(vector<int>& input)
{
for(int i=0; i<input.size(); i)
{
cout<<input[i]<<", ";
}
return;
}
void dfs(int indexStringA, string& stringA, int indexStringB, string& stringB, int& quantity)
{
if(stringA.size()==0)
{
return;
}
if(stringB.size()==0)
{
return;
}
if(visitedStringA[indexStringA]==1)
{
return;
}
if(visitedStringB[indexStringB]==1)
{
return;
}
visitedStringA[indexStringA]=1;
if(stringA[indexStringA]==stringB[indexStringB])
{
visitedStringB[indexStringB]=1;
marked[indexStringA]=1;
indexStringB;
}
for(int nextIndexStringA=(indexStringA 1); nextIndexStringA<stringA.size(); nextIndexStringA)
{
dfs(nextIndexStringA, stringA, indexStringB, stringB, quantity);
}
if(indexStringA==0)
{
for(int i=0; i<stringA.size(); i)
{
if(marked[i 1]<stringA.size())
{
if(marked[i]!=marked[i 1])
{
quantity;
}
}
}
}
return;
}
void solve()
{
string stringA="gamergirls";
string stringB="merils";
int inputQuantity=0;
cout<<"Before, inputQuantity <- "<<inputQuantity<<endl;
dfs(0, stringA, 0, stringB, inputQuantity);
cout<<"After, inputQuantity <- "<<inputQuantity<<endl;
return;
}
int main()
{
solve();
return 0;
}
結果如下：
Before, inputQuantity <- 0
After, inputQuantity <- 5
解釋。
如果輸入字串的大小stringA等于0，則遞回函式dfs()必須終止執行：
if(stringA.size()==0)
{
return;
}
如果輸入字串的大小stringB等于0，則遞回函式dfs()必須終止執行：
if(stringB.size()==0)
{
return;
}
如果訪問了具有具體索引indexStringA的 string 中的具體符號stringA，則遞回函式dfs()必須終止執行：
if(visitedStringA[indexStringA]==1)
{
return;
}
如果訪問了具有具體索引indexStringB的 string 中的具體符號stringB，則遞回函式dfs()必須終止執行：
if(visitedStringB[indexStringB]==1)
{
return;
}
如果符號，具有索引indexStringA和屬于stringA，等于混凝土符號，具有索引indexStringB和屬于stringB，因此，目前的索引indexStringB將被訪問visitedStringB[indexStringB]=1;。此外，將執行stringB到對應于命令的下一個索引的轉換 indexStringB;。的兩個碼元的對應的事實stringA和stringB將被分配到的放慢引數marked為marked[indexStringA]=1;：
if(stringA[indexStringA]==stringB[indexStringB])
{
visitedStringB[indexStringB]=1;
marked[indexStringA]=1;
indexStringB;
}
At the rise from the depth of the rescursive tree and at the achieving of the index indexStringA is equal to 0, the two neighboring items marked[i] and marked[i 1] will be considered. If these two items marked[i] and marked[i 1] are equal to 0 and 1 correspondingly or equal to 1 and 0 correspondingly, therefore, the parameter quantity will be increased on 1. The parameter quantity has the sense the minimum number of slices required to make stringA equal to stringB:
if(indexStringA==0)
{
for(int i=0; i<stringA.size(); i)
{
if(marked[i 1]<stringA.size())
{
if(marked[i]!=marked[i 1])
{
quantity;
}
}
}
}
If the next commands will be performed:
cout<<"marked <- ";
showContentVector(marked);
Therefore, the output will be:
marked <- 0, 0, 1, 1, 1, 0, 1, 0, 1, 1,
uj5u.com熱心網友回復：
如在評論中提到通過您的制約，我建議一個O（一種? BN）解決方案，其中
An是字串的長度A和Bn為字串的長度B。空間的復雜性將是
O(An)其中An的字串的長度A。
演算法：
我們先用長度簡單的檢查
A和B。如果B更長，則回傳-1。如果兩者具有相同的長度，如果它們相同，則回傳0，否則回傳-1。對于
A.length()>B.length(),我們檢查每個可能的
A長度B為 1 的長度的子序列。對于您的示例，bits我下面代碼中的陣列最初看起來像，0 0 0 0 1 1 1 1 1 1這個
bits陣列基本上意味著我們將檢查它的每一個可能的排列，包括上面的排列，看看是否有任何子序列A與此匹配。該1位應與 中的相應字符匹配B，否則排列失敗。如果有任何
bits匹配排列，我們將計算否。使其成功所需的削減。對于您的示例，bits陣列的排列如下所示，0 0 1 1 1 0 1 0 1 1 ------------------- g a m e r g i r l s正如你在上面看到的，我們有 6 個
0s 和1s段。最后，我們只取最小的所有可能性并回傳它。
主要代碼：
int min_cuts = Integer.MAX_VALUE;
do{
int ptr = 0;
for(int i=0;i<bits.length && ptr < B.length(); i){
if(bits[i] == '1'){
if(A.charAt(i) == B.charAt(ptr)){
ptr ;
}else{
break;
}
}
}
if(ptr == B.length()){
min_cuts = Math.min(min_cuts, getCuts(bits) - 1);
}
}while(nextPermutation(bits));
完整的在線演示
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/401172.html
上一篇：vb.net新年第四個星期二
下一篇：函式回傳“無”Python