Hidden in Order

Easy

You are given two strings, word and text. Can you get word by crossing out some letters of text (possibly none) without reordering the ones that remain? In other words, every letter of word must appear in text in the same order, though not necessarily next to each other. Return True if so and False otherwise. An empty word is hidden in any text.

Example 1

word="ant", text="planetary" → True

a at index 2, n at index 3 and t at index 5 appear in order, so the answer is True.

Example 2

word="tar", text="planetary" → True

t at index 5, then a at index 6, then r at index 7: the order holds, so True. For "rat" the answer would be False, since nothing follows the r but y.

Example 3

word="cat", text="concrete" → False

There is no a in concrete, so the answer is False.

Constraints

0 ≤ len(word) ≤ 100
0 ≤ len(text) ≤ 10⁴
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium Counting Palindromic Pieces of a String Medium Falling Domino Row Medium Word Growth Chain Medium Mirror Chunk Split Hard

Input

word="ant", text="planetary"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.