java - 需要建议解决递归算法以确定字符串是否是其他两个字符串的混洗

Question

我正在尝试创建一个递归算法来确定字符串 c 是否是字符串 a 和 b 的有序洗牌。有序洗牌意味着字符串 c 是由字符串 a 和 b 的字符以仍然保持两个字符串从左到右的顺序散布的方式组成的。

我已经尝试了这个算法的代码并且它在某种程度上有效，但是我在尝试测试某个打乱的单词时遇到了一个问题，如下面的代码所示。我认为这与我的 if 语句中的索引错误有关，但是无法找到修复此语句或绕过它的方法，非常感谢任何反馈或指导。

public class StringShuffleTest {

    public static boolean isOrderedShuffle(String a, String b, String c){
        //boolean to determine if String c is an ordered shuffle.
        boolean isShuffled = false;
        //variables for the size of Strings a, b and c.
        int n = a.length();
        int m = b.length();
        int len = c.length();

        //if the length of c is not the length of a + b return false.
        if (len != (n + m)){
            return isShuffled;
        }

        //if the length of a or b is 0, and c equals a or b, return true, otherwise,
        //return false.
        if (n == 0 || m == 0){
            if (c.equals(a) || c.equals(b)){
                return true;
            }
            else
                return isShuffled;
        }

        //if String a has length 1, remove String a from String c and make String a empty.
        if (n == 1){
                c = c.substring(0, c.indexOf(a.charAt(0))) + c.substring(c.indexOf(a.charAt(0)) +1);
                a = "";
                return isOrderedShuffle(a, b, c);

            }

        else
        //Recursive algorithm to determine if String c is an ordered shuffle of a and b.
        if (c.indexOf(a.charAt(0)) >= 0){

            int indexOfFirst = c.indexOf(a.charAt(0));
            int indexOfSecond = c.indexOf(a.charAt(1));

            if (indexOfFirst <= indexOfSecond){
            c = c.substring(0, indexOfFirst) + c.substring(indexOfFirst +1);
            a = a.substring(1, n);
                System.out.println(a);
                System.out.println(c);                   
            return isOrderedShuffle(a, b, c);
            }
            else
                return isShuffled;
        }

    return isShuffled;         
    }       

public static void main(String[] args) {

    System.out.println(StringShuffleTest.isOrderedShuffle("castle", "cat", "catcastle")); 

}

}

Answer 1

您可以通过创建一个调用递归方法的方法来简化它，例如:

private static String a, b, c;

public static boolean isOrderedShuffle(String a, String b, String c) {
    if (a.length() + b.length() != c.length())
        return false;
    StringShuffleTest.a = a; StringShuffleTest.b = b; StringShuffleTest.c = c;
    return isOrderedShuffle(0, 0);
}

private static boolean isOrderedShuffle(int n, int m) {
    if (n + m == c.length())
        return true;
    if (n < a.length() && a.charAt(n) == c.charAt(n + m) && isOrderedShuffle(n + 1, m))
        return true;
    if (m < b.length() && b.charAt(m) == c.charAt(n + m) && isOrderedShuffle(n, m + 1))
        return true;
    return false;          
}