Array Algorithm: Validate Subsequence 原创

1435-郭同学

发表文章数:18

首页 » 算法 » 正文

算法刷题系列 Algorithm


Difficulty:easy

Validate Subsequence

Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.
A subsequence of an array is a set of numbers that aren’t necessarily adjacent in the array but that are in the same order as they appear in the array. For instance, the numbers [1, 3, 4] form a subsequence of the array [1, 2, 3, 4] , and so do the numbers [2, 4] . Note that a single number in an array and the array itself are both valid subsequences of the array.

Sample input:

array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]

output

ture

Solution 1:
while loop
O(n) time | O(1) space

def isValidSubsequence(array, sequence):
    # Write your code here.
	arrIdx = 0
	seqIdx = 0
	while arrIdx < len(array) and seqIdx < len(sequence):
		if sequence[seqIdx] == array[arrIdx]:
			seqIdx += 1
		arrIdx += 1

	return seqIdx == len(sequence)

Solution 2:
for loop
O(n) time | O(1) space

def isValidSubsequence(array, sequence):
	seqIdx = 0
	for value in array:
		if seqIdx == len(sequence):
			break
		if sequence[seqIdx] == value:
			seqIdx += 1
	return seqIdx == len(sequence)

from AlgoExpert

未经允许不得转载:作者:1435-郭同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Array Algorithm: Validate Subsequence 原创》 发布于2021-02-06

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录