字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 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]!='' && 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,如此看来,此方法还是大有可为的。
总结一下思路:
class Solution {
var dic: [Character:Array<Int>]!
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进行投诉反馈,一经查实,立即删除!