本文介绍: 给定字符串st判断s是否t的子序列字符串一个子序列是原始字符串删除一些(也可以删除字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace“是”abcde“的一个子序列,而”aec“不是)。

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

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

进阶:

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

示例 1:

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

示例 2:

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

提示


思路还是挺简单的, 使用C语言更能体现出思路。

  1. 取出s字符串中的一个字符
  2. 取出t字符串中的一个字符
  3. 匹配这2个字符的值
    1. 字符一致,s字符后移,取下一个;t字符后移,取下一个
    2. 字符不一致,t字符后移,取下一个
  4. 最终结束的时候,
    1. 如果s字符串在结束位置说明匹配成功,返回true
    2. 如果s字符串不在结束位置说明是t字符先结果匹配失败返回false 
bool isSubsequence(char * s, char * t){
    int i=0,j=0;
    for (;s[i]!='' && t[j]!='';) {
        char sChar = s[i];
        char tChar = t[j];
        if (sChar == tChar) {
            i++;
        }
        t++;
    }

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

}

 使用swift也是同样的思路,但是swift中的字符串确实不好用,写起来没有c语言简洁思路清晰。

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> 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
    }
}

2种算法时间复杂度都是O(N) ,空间复杂度都是O(1).

对于思考题

思路1:

把T所有的可能列举出来,然后构造成一个集合,后续的结果需要匹配集合中有没有子串即可

比如 T=“abc”, 列举出所有就是8种组合,“”, “a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”,

然后估算了一下,t的长度是10^4,  枚举出来结果的数量得有 2^n,n=10^4, 这个数太大了,已经算不出来了,2^100次方用科学计数法表示是1.27×10^30, 已经30个零了。

方法想想就行,打住打住。只有t的长度比较小的时候才能发挥作用。

思路2:

由于S很多,而T不变,所以要深度挖掘T的潜力,由于总共只有26个字母可以根据T构造出26个数组

以下面的数据为例,“dbceafcdbf” ,  比如A数组存放的是所有a字母出现的位置,A={5},  B={2,9},C={3,7},D={1,8}, …

这样出现一个S时,不需要遍历寻找T中对应匹配的位置,只需要对应字母数组中查位置即可跳跃式的查找结果时间复杂度和T的长度无关,只和S的长度有关。而S的长度小于100,如此看来,此方法还是大有可为的。

总结一下思路:

  1. 根据T字符串生成系列数组
  2. 遍历S字符串,
  3. 已S字符串的单个字符作为key,从对应数组中找匹配最小下表
    1. 能找到,更新T的查找进度,下次从最小下表+1继续查
    2. 找不到,说明匹配返回false
  4. 能遍历完S, 说明是子序列,返回true

生成数组长这样

{
“a”:[1,2],
b“:[4,7],
“c”:[3,5],
d“:[6],
……
}

swift 参考代码如下

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
    }
}

 虽然单次看效率不高,但是针对思考题场景应该是能优化很多。

原文地址:https://blog.csdn.net/u014600626/article/details/128138074

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_19105.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注