java - 对字符串使用一些特定的附加操作检查它是否可以转换为其他字符串

Question

给定两个字符串 - 一个初始字符串和一个目标字符串。然后，您的代码必须确定初始字符串是否可以通过向其附加 P 或 Q(重复)以某种方式转换为目标字符串。

但是，要附加 P 或 Q，您必须遵循以下两条规则: 将 P 添加到末尾 反转字符串并将 Q 附加到末尾

示例 -

示例:

初始:PQQ， 目标:PQQP，

输出:true

<小时/>

首字母:PQQ 目标:QQPQPPPP

输出:true

<小时/>

首字母:P 目标:PQPQQQ

输出:假

我尝试通过简单的递归来解决这个问题，但无法发现它适用于所有上述测试用例。我不知道我的方向是否正确。我欢迎所有建议，请就此提出建议。以下是我的方法

public class Convert {

     boolean isMatch(String s1 , String s2){
        if(s1.equals(s2))
            return true;
        String  s3 = s1.concat("P");
        StringBuilder input1 = new StringBuilder();
        input1.append(s1);
        String  s4 = input1.reverse().toString();
        s4 = s4.concat("Q");    
        return isMatch(s3, s2) || isMatch(s4,s2);   
    }

    public static void main(String[] args) {

        String s1 = "PQQ";
        String s2 = "PQQP";
        Convert c1 = new Convert();
        boolean res = c1.isMatch(s1, s2);
        System.out.println(res);
    }
}

Answer 1

你们很接近。您所需要的只是退出标准:

if (s1.length() > s2.length())
    return false;

放在正下方

if(s1.equals(s2))
        return true;

如果 s1 比 s2(目标字符串)长，请停止寻找解决方案，因为 s1 不可能通过添加更多内容而变成 s2(它已经太长了)。

如果没有退出条件，您将永远循环。例如“啊哈，字符串 PPPPPP 不等于字符串 PP，让我们看看字符串 PPPPPP 或 PPPPPPQ 是否相等”，等等，等等，...