Leetcode: Is Subsequence
LeetCode is Subsequence
2023-09-11 14:14:07 时间
Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not). Example 1: s = "abc", t = "ahbgdc" Return true. Example 2: s = "axc", t = "ahbgdc" Return false. Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Basic Solution: DP, O(mn) time, O(m) space, m is the size of s, n is the size of t
1 public class Solution { 2 public boolean isSubsequence(String s, String t) { 3 if (s.length() == 0) return true; 4 boolean[] dp = new boolean[s.length()+1]; 5 dp[0] = true; 6 for (int i=1; i<=t.length(); i++) { 7 for (int j=s.length(); j>=0; j--) { 8 if (dp[j] || t.charAt(i-1)==s.charAt(j-1) && dp[j-1]) 9 dp[j] = true; 10 } 11 if (dp[s.length()]) return true; 12 } 13 return false; 14 } 15 }
Greedy Solution: O(n) time, O(1) space
1 public class Solution { 2 public boolean isSubsequence(String s, String t) { 3 if (s.length() == 0) return true; 4 int match = 0; 5 for (int i=0; i<t.length(); i++) { 6 if (t.charAt(i) == s.charAt(match)) { 7 match++; 8 } 9 if (match == s.length()) return true; 10 } 11 return false; 12 } 13 }
Follow Up:
The best solution is to create a map for String t, key is char, value is the index of appearance in ascending order
1 public boolean isSubsequence(String s, String t) { 2 List<Integer>[] idx = new List[256]; // Just for clarity 3 for (int i = 0; i < t.length(); i++) { 4 if (idx[t.charAt(i)] == null) 5 idx[t.charAt(i)] = new ArrayList<>(); 6 idx[t.charAt(i)].add(i); 7 } 8 9 int prev = 0; 10 for (int i = 0; i < s.length(); i++) { 11 if (idx[s.charAt(i)] == null) return false; // Note: char of S does NOT exist in T causing NPE 12 int j = Collections.binarySearch(idx[s.charAt(i)], prev); 13 if (j < 0) j = -j - 1; 14 if (j == idx[s.charAt(i)].size()) return false; 15 prev = idx[s.charAt(i)].get(j) + 1; 16 } 17 return true; 18 }
相关文章
- 一道 LeetCode 周赛的题目,让我自信满满!
- Is there a way to detect if a browser window is not currently active?
- Leetcode 887.鸡蛋掉落(Hard)
- [LeetCode] Remove Duplicates from Sorted List II
- [LeetCode]剑指 Offer 57. 和为s的两个数字
- 【LeetCode】167. Two Sum II - Input array is sorted
- 【LeetCode】94. Binary Tree Inorder Traversal (3 solutions)
- 【LeetCode-面试算法经典-Java实现】【015-3 Sum(三个数的和)】
- 【leetcode】23:合并k个生序链表
- [LeetCode] 1232. Check If It Is a Straight Line 缀点成线
- [LeetCode] 1036. Escape a Large Maze 逃离巨型迷宫
- [LeetCode] 852. Peak Index in a Mountain Array 山形数组的顶峰坐标
- [LeetCode] Most Profit Assigning Work 安排最大利润的工作
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- [LeetCode] 409. Longest Palindrome 最长回文串
- [LeetCode] 382. Linked List Random Node 链表随机结点
- leetcode 785. Is Graph Bipartite判断二分图 (中等)