摘要：例如，，則的其中一種組合是的子串，然后返回。如果從題目給出的例子來窮舉，一共種組合，很容易窮舉出來，但是字符串長度非常大的時(shí)候，怎么辦呢所以，窮舉的辦法被我排除了。

這道算法題在前端面試中可能遇到，據(jù)說某條出過這題。

查找字符串B的字符任意一種組合是否是字符串A的子串。
例如 A=abc123，B=cba，則B的其中一種組合abc是A的子串，然后返回true。

題目的出處已經(jīng)無從考究，接下來我們從JavaScript的角度來封裝這樣一個(gè)功能函數(shù)。

一開始看到這道題，你會(huì)想到什么？
我想到的是先列舉出B的所有排列組合，存到數(shù)組里面，然后遍歷，判斷是否有組合包含在A中，如果有返回true，否則返回false。
如果從題目給出的例子來窮舉，一共6種組合，很容易窮舉出來，但是字符串長度非常大的時(shí)候，怎么辦呢？
所以，窮舉的辦法被我排除了。

這名字聽起來很奇怪，怎么個(gè)思路呢？

1、A的排序肯定是不變的，既然可變的我們很難下手，那么可以從不變的地方入手，以不變應(yīng)萬變。

2、看字符串可能不太習(xí)慣，我把A和B都轉(zhuǎn)換成數(shù)組。

let a = A.split("") // [a, b, c, 1, 2, 3]
let b = B.split("") // [c, b, a]

3、先過濾數(shù)組為空的情況，如果a或者b為空，那么不需要比較，返回false。

if (a.length === 0 || b.length === 0) {
    return false
}

4、只看數(shù)組b，可以有6種排列組合，[c,b,a]，[a,b,c]，[a,c,b]，[b,a,c]，[b,c,a]，[c,a,b]。還記得第1步說的，我們不管b有多少種組合，都從a入手。

// a = [a, b, c, 1, 2, 3]
for (let j = 0; j < a.length; j++) { 

}

5、遍歷a有什么作用呢？接下來我為大家揭曉何為標(biāo)記刪除法，允許我小小解釋一下該方法，分為2個(gè)核心，“標(biāo)記”和“刪除”，“標(biāo)記”是指標(biāo)記當(dāng)前數(shù)組a遍歷的位置，“刪除”是指刪除數(shù)組b中的元素。

這樣說可能不太懂，先不看代碼，我用數(shù)組來模擬一下執(zhí)行過程。

初始化的值
a = [a, b, c, 1, 2, 3]
b = [c, b, a]
==================================================
當(dāng)遍歷a的時(shí)候，j從0開始，遍歷到a.length-1結(jié)束
==================================================
j = 0 // 給a里的字符加""，做個(gè)標(biāo)記，表示當(dāng)前遍歷的下標(biāo)位置
a = ["a", b, c, 1, 2, 3]
==================================================
然后我們發(fā)現(xiàn)數(shù)組b存在當(dāng)前的字符"a"，執(zhí)行刪除操作
b = [c, b]
==================================================
j = 1 // 數(shù)組a遍歷到第二個(gè)字符
a = [a, "b", c, 1, 2, 3] // 標(biāo)記
b = [b] // 刪除
==================================================
j = 1 // 數(shù)組a遍歷到第三個(gè)字符
a = [a, b, "c", 1, 2, 3] // 標(biāo)記
b = [] // 刪除
==================================================
現(xiàn)在我們看到b數(shù)組變成空了，則證明b的任意一種排列存在于a中

6、上一步描述的情況是最簡單的狀態(tài)，剛好在A字符中存在不間斷的字符組合。我們把A改一下，變成 A = a1b2c3abc。即使變復(fù)雜了，我們依舊可以使用標(biāo)記刪除發(fā)來做，只是稍微做一點(diǎn)處理。

初始化的值
a = [a, 1, b, 2, c, 3, a, b, c]
b = [c, b, a]
==================================================
當(dāng)遍歷a的時(shí)候，j從0開始，遍歷到a.length-1結(jié)束
==================================================
j = 0 // 給a里的字符加""，做個(gè)標(biāo)記，表示當(dāng)前遍歷的下標(biāo)位置
a = ["a", 1, b, 2, c, 3, a, b, c]
==================================================
然后我們發(fā)現(xiàn)數(shù)組b存在當(dāng)前的字符"a"，執(zhí)行刪除操作
b = [c, b]
==================================================
j = 1 // 數(shù)組a遍歷到第二個(gè)字符
a = [a, "1", b, 2, c, 3, a, b, c] // 標(biāo)記
// 突然發(fā)現(xiàn)第2個(gè)字符是1，現(xiàn)在該怎么辦？我們只需要把數(shù)組b恢復(fù)初始狀態(tài)即可

b = [c, b, a] // 恢復(fù)初始狀態(tài) 
==================================================
接下來繼續(xù)遍歷，重復(fù)上面的處理步驟，直到數(shù)組b為空或者數(shù)組a遍歷完成，返回結(jié)果

7、JavaScript代碼實(shí)現(xiàn)
下面是第6步說明的代碼實(shí)現(xiàn)，從代碼中可以看到，不管B字符有多少排列組合，我們始終只需要遍歷A的所有字符即可，內(nèi)部實(shí)現(xiàn)也是用空間換時(shí)間。

// 遍歷數(shù)組 a
    for (let j = 0; j < a.length; j++) {
        // 數(shù)組 b不為空，下一步
        if (b.length > 0) {
            // 數(shù)組a存在當(dāng)前遍歷的數(shù)組b的元素
            if (b.indexOf(a[j]) > -1) {
                // 刪除b數(shù)組中匹配到的第一個(gè)對(duì)應(yīng)下標(biāo)的元素
                b.splice(b.indexOf(a[j]), 1)
                if (b.length === 0) {
                    // 如果數(shù)組b全部被刪除了，則證明b是a的子串
                    return true
                }
            } else {
                // 數(shù)組b不存在當(dāng)前遍歷的數(shù)組b的元素，恢復(fù)b數(shù)組
                b = B.split("")
            }
        } else {
            // 數(shù)組 b為空返回true
            return true
        }
    }

與其他前端工程師的交流中，我還了解到了其他的解題思路，有些很有趣，比如考慮使用Map或Set、滑塊區(qū)間比較等，不過我沒有去用代碼實(shí)現(xiàn)過，如果你有其他的方法，可以在下面留言交流。

評(píng)論區(qū)有人指出不能覆蓋某些場(chǎng)景的測(cè)試用例，所以我對(duì)上面的具體過程做了改進(jìn)，下面是改進(jìn)后的源碼。
增加了2個(gè)字段，isBack和isRestart，isRestart用來標(biāo)記是否重新在當(dāng)前位置遍歷，isBack判斷是否對(duì)數(shù)組遍歷的下標(biāo)進(jìn)行回退一個(gè)單位。

var A = "abc123"
  , B = "cba"
function interface(A, B) {
    // 將A和B轉(zhuǎn)成數(shù)組
    let a = A.split("")
    let b = B.split("")
    if (a.length === 0 || b.length === 0) {
        return false
    }
    let isBack = false, isRestart = 0
    // 遍歷數(shù)組 a
    for (let j = 0; j < a.length; j++) {
        // 數(shù)組 b不為空，下一步
        if (b.length > 0) {
            isBack = false
            // 數(shù)組a存在當(dāng)前遍歷的數(shù)組b的元素
            if (b.indexOf(a[j]) > -1) {
                // 刪除b數(shù)組中匹配到的第一個(gè)對(duì)應(yīng)下標(biāo)的元素
                b.splice(b.indexOf(a[j]), 1)
                if (b.length === 0) {
                    // 如果數(shù)組b全部被刪除了，則證明b是a的子串
                    return true
                }
            } else {
                if (isRestart !== 0) {
                    isBack = false
                } else {
                    isBack = true
                }
                // 數(shù)組b不存在當(dāng)前遍歷的數(shù)組b的元素，恢復(fù)b數(shù)組
                b = B.split("")
                if (isBack) {
                    j -= 1
                    isRestart = 0
                }
                isRestart++
            }
        } else {
            // 數(shù)組 b為空返回true
            return true
        }
    }
    return false
}
interface(A, B)