LeetCode392. 判断子序列_代码007(未授权)

本文介绍: 给定字符串 s和t，判断 s 是否为t的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace“是”abc de“的一个子序列，而”ae c“不是）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k &g t;= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

bool isSubsequence(char * s, char * t){
    int i=0,j=0;
    for (;s[i]!='' &amp;&amp; t[j]!='';) {
        char sChar = s[i];
        char tChar = t[j];
        if (sChar == tChar) {
            i++;
        }
        t++;
    }

    if (s[i]=='') {
        return true;
    }
    return false;

}

class Solution {
    func isSubsequence(_ s: String, _ t: String) -&gt; Bool {
        var s = s
        if s.isEmpty { return true }
        for char in t {
            if let sFirst = s.first, sFirst == char {
                s.removeFirst()
            }
            if s.isEmpty {
                return true
            }
        }
        return false
    }
}

class Solution {

    var dic: [Character:Array<Int&gt;]!
    func configTDic(t: String) {
        // 构造t组成的数组,简单写个json示意一下,只需要生成依次即可
        /*
         {
            "a":[1,2],
            "b":[4,7],
            "c":[3,5],
            "d":[6],
         }
         */
        var dic = [Character:Array<Int>]()
        for (idx,tChar) in t.enumerated() {
            if var array = dic[tChar] {
                array.append(idx)
                dic[tChar] = array
            } else {
                var array = [Int]()
                array.append(idx)
                dic[tChar] = array
            }
        }
        self.dic = dic
    }

    func isSubsequence(_ s: String, _ t: String) -> Bool {

        if self.dic == nil {
            self.configTDic(t: t)
        }
        var tempDic = self.dic!
        // tIndex记录查询到t的下表
        var tIndex = 0
        for (_,sChar) in s.enumerated() {
            if let array = tempDic[sChar] {
                // 比如数组是[1,5,7],tIndex=3, 此时需要舍弃1,取5,并把tIndex更新成6
                let filterArray = array.filter { value in
                    value >= tIndex
                }
                // 数组中找不到合适值,T中没有对应字符,返回false
                if filterArray.isEmpty {
                    return false
                }
                // filterArray.first中的字符已经使用了,下次匹配不能再使用同一字符
                tIndex = filterArray.first! + 1
                tempDic[sChar] = filterArray
            } else {
                // 取不出数组,说明T中没有这个字母,返回false
                return false
            }
        }

        return true
    }
}