你可以认为 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 }
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 }
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
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)
import java.util.Scanner; public class Main21 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String t = sc.nextLine(); String s = sc.nextLine(); int p1=0; int p2=0; for(int i=0;i<t.length();i++){ if(t.charAt(p1)==s.charAt(p2)){ p1++; p2++; }else if(t.charAt(p1) != s.charAt(p2)) p1++; if(p1>t.length()||p2>s.length()){ break; } } System.out.println(p2>s.length()-1); } }
public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextLine()) { // 注意 while 处理多个 case String s = in.nextLine(); String t = in.nextLine(); int sIndex = 0; int tIndex = 0; for (;tIndex < t.length() && sIndex < s.length(); tIndex++) { if (t.charAt(tIndex) == s.charAt(sIndex)) { sIndex++; } } System.out.println(sIndex == s.length()); } }
import Foundation while let line = readLine() { let subArray = Array(line) var supArray = Array(readLine()!) var index = 0 var flag = false for i in 0..<supArray.count { if supArray[i] == subArray[index] { index += 1 } if index == subArray.count { flag = true break } } print(flag) // let parts = line.split(separator: " ") // print(Int(parts[0])! + Int(parts[1])!) }
class Solution: def isSubseq(self, s: str, t: str) -> bool: n = 0 for i in s: for j in range(n, len(t)): if i == t[j]: n = j + 1 break else: return False return True s = 'axc' t = 'ahbgdc' print(Solution().isSubseq(s, t))
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { // Write your code here const lineArr = []; while ((line = await readline())) { lineArr.push(line); } const tempArr = []; const sArr = lineArr[0].split(""); const tArr = lineArr[1].split(""); let start = 0 for(let i = 0; i < sArr.length; i++) { for(start; start < tArr.length; start++) { if(tArr[start] === sArr[i]) { tempArr.push(tArr[start]) break } } } if (tempArr.join("") === lineArr[0]) { console.log(true); } else { console.log(false); } })();