时间戳

首页 > 解决方案 > 这个回溯代码如何确保两个字符串没有共同的元素？

c++ - 这个回溯代码如何确保两个字符串没有共同的元素？

问题描述

我在 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;
        string s1, s2;
        helper(s, s1, s2, 0);
        
        return res;
    }
};

这有效并获得了 ACed，但我不确定它如何确保两个字符串是不相交的。我期待进行检查以确保这一点并res在两个字符串不相交时进行更新。

是什么赋予了？

谢谢！

标签： c++algorithmbacktrackingdisjoint-sets

解决方案

乍一看，它看起来像 DP（动态编程）。

最初的问题听起来像这样。

给定一个字符串 s，找到 s 的两个不相交的回文子序列，使得它们的长度的乘积最大化。

helper解决了这个问题的更通用的版本：

给定一个字符串 s，找到 s 的两个不相交的回文子序列，它们具有指定的前缀 s1 和 s2，使得它们的长度的乘积最大化。

它使用递归来做到这一点。我们可以将所有可以想象的情况分为三类：

  1. 第一个字母是第一个子序列的一部分，在这种情况下，我们将此字母附加到前缀s1并解决字符串其余部分的相同问题s。
  2. 第一个字母是第二个子序列的一部分，在这种情况下，我们将这个字母附加到前缀上s2，并为字符串的其余部分解决相同的问题s。
  3. 第一个字母既不是第一个子序列的一部分，也不是第二个子序列的一部分，在这种情况下，我们可以忽略这个字母，只解决字符串其余部分的问题s。

这三个递归调用helper正好对应这三种情况。从这些案例的构造中，您可能会看到没有一个字母可能同时出现在两个序列中。

越来越接近问题。helper在对初始字符串的每个字符的递归调用期间，s只能出现在s1（第一种情况）或s2（第二种情况）或被拒绝（第三种情况）。您可能会在代码中准确地看到这一点。角色被放入s1然后递归调用发生，然后它被弹出，然后它被放入s2，然后递归调用发生，它被弹出，然后再次递归调用。

推荐阅读