面试算法题一则

就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

/**
 * User: SunDP
 * Date: 12-12-15
 * Time: 下午11:14
 */
public class StringTest {

    public static void main(String[] args) {
        int flagX = 0, flagY = 0;
        String a = "aaaaaaaa";
        String b = "aaaaaaba";
        String c = "aaaaaaaabaaaaaaa";
        if (a.length() + b.length() != c.length())
            System.out.println(false);
        else
            System.out.println(dsp(flagX, flagY, a, b, c));
    }

    private static boolean dsp(int flagX, int flagY, String a, String b, String c) {
        if (flagX == a.length() && flagY == b.length())
            return true;
        if (flagX != a.length() && a.charAt(flagX) == c.charAt(flagX + flagY))
            if (dsp(flagX + 1, flagY, a, b, c))
                return true;
        if (flagY != b.length() && b.charAt(flagY) == c.charAt(flagX + flagY))
            if (dsp(flagX, flagY + 1, a, b, c))
                return true;
        return false;
    }
}