你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度n ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
进阶:时间复杂度,空间复杂度
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度n ~= 500,000),而 s 是个短字符串(长度 <=100)。
共两行,第一行为字符串s, 第二行为字符串t
字符串t的长度 1<=n<=500000
字符串s的长度 1<=m<=100
输出true或者是false,true表示是s是t的子序列,false表示s不是t的子序列
abc ahbgdc
true
axc ahbgdc
false
var boolen = function(str1,str2) { if (str1.length > str2.length) { return false } var first = str1.split('')[0] for (let a = 0; a <= str2.length; a++) { if (str2[a] === first) { if (str1.length > 0) { var strNew1 = str1.slice(1) var strNew2 = str2.slice(a) return boolen(strNew1,strNew2) } else { return true } } } return false }
def s_isT(s, t): n = len(s) m = len(t) if n > m: return 'false' p1 = p2 = 0 res = "" while p1 < n and p2 < m: if s[p1] == t[p2]: res += s[p1] p1 += 1 p2 += 1 else: p2 += 1 if res == s: return 'true' else: return 'false' while True: try: s = input() t = input() print(s_isT(s, t)) except: break
function decide(str1, str2) { str2 = str2.split('') str1 = str1.split('') if (str2.length < str1.length) return false; let num = str1.length let first = str1.shift() let counter = 0 for (let i = 0; i < str2.length; i++) { if (first === str2[i]) { counter++; first = str1.shift() } } return num === counter }
a = input().strip() b = input().strip() i = j = 0 while i < len(a) and j < len(b): if a[i] != b[j]: j += 1 else: i += 1 j += 1 if i == len(a): print('true') else: print('false')
public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNextLine()){ String s = sc.nextLine(); String t = sc.nextLine(); if(isSubStr(s,t)){ System.out.println("true"); } System.out.println("false"); } } private static boolean isSubStr(String s, String t){ char[] charS = s.toCharArray(); char[] charT = t.toCharArray(); int index = 0; for(int i = 0; i < charT.length; i++){ if(charT[i] == charS[index]){ index++; } if(index >= charS.length){ return true; } } return false; } }
class Solution: def isSon(self, s: str, m: str) -> bool: # 先将字符串列表化 s_ls = list(s) # print(s_ls) m_ls = list(m) # print(m_ls) # 设置结果变量flag flag = False # index用来记录上一次匹配成功的元素的位置 index = 0 # 外循环是变化慢的s_ls 内循环是变化快的m_ls for i,val1 in enumerate(s_ls): for j,val2 in enumerate(m_ls): # 若在m_ls中找到了s_ls的元素并且该元素的位置在上一个匹配上的元素的后面 if val1 == val2 and j >= index: # 更新index,结果设置为true index = j flag = True break else: flag = False # 若遍历完m_ls都没有找到与s_ls的元素相等的元素,说明s_ls not in m_ls,那就直接结束整个循环,返回false if flag == False: break print(str(flag).lower()) solution = Solution() solution.isSon('hgb', 'ahbgdc')
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("input zi chuan"); String childrenString = input.next(); System.out.println("input fu chuan"); String superString = input.next(); System.out.println(panduan(childrenString,superString)); } public static boolean panduan(String zc, String fc){ String s = fc; for(int i =0 ; i < zc.length();i++){ char ch = zc.charAt(i); //在父串中组合子串 s = s.substring(s.indexOf(ch)); if(s.indexOf(ch) == -1 ) return false; } return true; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { String t = sc.nextLine(); String s = sc.nextLine(); int fromIndex = 0; boolean flag = true; for (int i = 0; i < t.length(); i++) { int tmp = s.indexOf(t.charAt(i), fromIndex); if (tmp < 0) { flag = false; break; } fromIndex = tmp; // s = s.substring(tmp); } System.out.println(flag); } } }
const s = readline() let t = readline() let flag = true for (let i = 0; i< s.length;i++){ if(t.indexOf(s[i]) === -1){ flag = false console.log(false) break; }else{ t = t.slice(t.indexOf(s[i]) + 1) } } if(flag) console.log(true)