Java 字串交錯組成判斷：遞迴演算法驗證 C 是否由 A 與 B 交錯而成

題目

給定三個字串 A、B、C，判斷 C 是否由 A 與 B 交錯組成。條件是 C 包含且僅包含 A、B 的所有字符，且對應順序不改變。

遞迴程式碼範例

import java.util.*;

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        return chkMixture(A, B, C, A.length()-1, B.length()-1, C.length()-1);
    }

    public static boolean chkMixture(String A, String B, String C, int i, int j, int k) {
        if (k < 0) return true;
        if (i < 0) {
            return B.charAt(j) == C.charAt(k) && chkMixture(A, B, C, 0, j-1, k-1);
        }
        if (j < 0) {
            return A.charAt(i) == C.charAt(k) && chkMixture(A, B, C, i-1, 0, k-1);
        }
        boolean res1 = false, res2 = false;
        if (A.charAt(i) == C.charAt(k))
            res1 = chkMixture(A, B, C, i-1, j, k-1);
        if (B.charAt(j) == C.charAt(k))
            res2 = chkMixture(A, B, C, i, j-1, k-1);
        return res1 || res2;
    }
}

測試樣例

A="ABC", B="12C", C="A12BCC"，回傳 true。