我正在嘗試LeetCode上的這個問題:
給定一個字串s，找出兩個不相交的s的宮格子序列，使它們的長度之積達到最大。如果這兩個子序列沒有在相同的索引處選取一個字符，它們就是不相交的。 回傳兩個同位素子序列長度的最大可能乘積。 例如，如果s = "leetcodecom"，輸出應該是9（兩個字串是ete和cdc，等等）。
在網上的幫助下，我想出了下面的代碼：
class Solution {
public:
int res;
bool isPalindrome（string& s）{
int i=0, j=s.size()1;
while(i<j && s[i]==s[j]) {
i ;
j--;
}
return i>=j;
}
void helper(string& s, string& s1, string& s2, int start) {
if(start>=s.size() ) {
if(isPalindrome(s1) and isPalindrome(s2) ) {
res=max((int)res, (int)s1. size（）*（int）s2.size（））。
}
return;
}
s1 =s[start];
helper(s, s1, s2, start 1) 。
s1.pop_back（）。
s2 =s[start];
helper（s, s1, s2, start 1）。
s2.pop_back（）。
helper（s, s1, s2, start 1）。
}
int maxProduct(string s){
res=0;
字串s1，s2。
helper（s, s1, s2, 0）。
returnres。
}
};
這可以作業并獲得ACed，但我不確定它如何確保兩個字串是disjoint。 我希望能有一個檢查來確保這一點，并在兩個字串不相連時更新res。
什么原因？
謝謝！
uj5u.com熱心網友回復：
乍一看，它看起來像DP（動態編程）。
最初的問題聽起來是這樣的。
給定一個字串s，找到s的兩個不相交的宮格子序列，使它們的長度之積達到最大。
helper解決了這個問題的一個更通用的版本：
給定一個字串s，找到s的兩個不相交的宮格子序列，并指定前綴為s1和s2，使它們的長度之積達到最大。
它是通過遞回來實作的。我們可以將所有可以想象到的情況分成三類：
s1，并對字串s的其余部分解決同樣的問題。
s2，并對字串s的其余部分解決同樣的問題。
s的其余部分的問題。
對helper的三次遞回呼叫正好對應于這三種情況。從這些情況的構造中，你可以看到，沒有一個字母可以同時出現在兩個序列中。
越來越接近問題。在遞回呼叫helper期間，初始字串s的每個字符只能出現在s1（第一種情況）或s2（第二種情況）或被拒絕（第三種情況）。你可以在代碼中準確地看到這一點。字符被放入s1，然后發生遞回呼叫，然后它被彈出，然后它被放入s2，然后發生遞回呼叫，它被彈出，然后再次遞回呼叫。
uj5u.com熱心網友回復：
這段代碼確保了不連接性，因為helper中的兩個遞回Steop塊不曾在s1和s2中拉出同一個字符。
首先，對helper的每次呼叫都不會回傳，直到處理完字串為止，包括所有觸發的遞回情況。然后，pop_back將把各自的序列回傳到它的原始值，在這一級的遞回。
s1 =s[start];
helper（s, s1, s2, start 1）。
s1.pop_back（）。
s2 =s[start];
helper（s, s1, s2, start 1）。
s2.pop_back（）。
每當第一個塊完成，控制權落入第二個塊時，s1就會重新回到它進入這個遞回級別時的值。一些之前被放入s1的相同字符被添加到s2。但它們永遠不會同時出現在兩個地方。
helper（s, s1, s2, start 1）。
這一行推進遞回，搜索從所有位置開始的子序列。但是在這里，沒有任何字符被添加到s1或s2。只有start索引向前移動。因此，同樣地，由于沒有添加任何字符，所以不能添加任何普通字符。
在整個遞回程序中，s1和s2包含s的潛在交錯子序列，但是s的任何字符都沒有同時出現在s1和s2中。
這很難理解，因為它不是函式遞回，因為序列是通過參考傳遞的，并被破壞性地操作。這是一種迭代程序，它使用遞回為它提供了一個回溯堆疊；松散地說是一個下推自動機。它甚至不回傳一個值；它的輸出是對遞回之外的成員變數的副作用。
你必須直覺到，s2 =s[start];和s2.pop_back()是平衡的、成對的堆疊式操作，它們將序列帶到相同的狀態，而不管下面的遞回中發生了什么（因為下面的遞回執行了相同的平衡推/放對）。此外，下面的遞回總是在start 1，并且只向右移動，所以它永遠不會向兩個子序列添加相同的字符。因此，我們可以看到在同一個框架中存在一個區域的相互排斥，再加上對下部遞回框架的相互排斥。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/308826.html
標籤：