题解 | #交织子序列#

本地常规场景很简单，只要将其中一个字符串的内容挨个去除即可，但若遇到字串1和字串2中间有重复的字母则会出现失败的可能，
例如s:qwca x:acbd,t:qwacbcad;
如果你是按顺序去除的S，则剩余的值为abcd
所以我们要考虑到t中包含s的多种情况，可用队列的形势将t去除s后的剩余子串都保存，看是否有和x相同的

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param x string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    public boolean isInterleave (String s, String x, String t) {
        // write code here


        if (t.length() == (s.length() + x.length())) {
            List<String> listStr = createNewStr(s, t, 0);
            return listStr.contains(x);
        }

        return false;
    }

    /**
     *   @param index 当前准备去除S的字母下标
     */
    public List<String> createNewStr(String s, String t, int index) {
        List<String> listStr = new ArrayList<>();
        if (index == s.length()) {
            listStr.add(t);
            return listStr;
        }
        String tStr = new String(t);
        String sStr = new String(s);
        String value = String.valueOf(s.charAt(index));
        
        // 当前字符串在t出现的次数      
        int num = t.length() - (t.replaceAll(value, "")).length();
        for(int i =0; i < num; i ++) {
            // 当前首个的位置
            int currentIndex = tStr.indexOf(value) + i;
            tStr = tStr.replaceFirst(value, "");
            listStr.addAll(createNewStr(s, t.substring(0, currentIndex) + t.substring(currentIndex + 1), index + 1));
        }
        return listStr;
    }

}