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

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

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

題目的出處已經無從考究，接下來我們從JavaScript的角度來封裝這樣一個功能函數。

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

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

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

2、看字符串可能不太習慣，我把A和B都轉換成數組。

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

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

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

4、只看數組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有什么作用呢？接下來我為大家揭曉何為標記刪除法，允許我小小解釋一下該方法，分為2個核心，“標記”和“刪除”，“標記”是指標記當前數組a遍歷的位置，“刪除”是指刪除數組b中的元素。

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

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

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

初始化的值
a = [a, 1, b, 2, c, 3, a, b, c]
b = [c, b, a]
==================================================
當遍歷a的時候，j從0開始，遍歷到a.length-1結束
==================================================
j = 0 // 給a里的字符加""，做個標記，表示當前遍歷的下標位置
a = ["a", 1, b, 2, c, 3, a, b, c]
==================================================
然后我們發現數組b存在當前的字符"a"，執行刪除操作
b = [c, b]
==================================================
j = 1 // 數組a遍歷到第二個字符
a = [a, "1", b, 2, c, 3, a, b, c] // 標記
// 突然發現第2個字符是1，現在該怎么辦？我們只需要把數組b恢復初始狀態即可

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

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

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

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

評論區有人指出不能覆蓋某些場景的測試用例，所以我對上面的具體過程做了改進，下面是改進后的源碼。
增加了2個字段，isBack和isRestart，isRestart用來標記是否重新在當前位置遍歷，isBack判斷是否對數組遍歷的下標進行回退一個單位。

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