Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Pre Processing Time : O(words.length)
- *
- * Time Complexity: O(S.length() + Summation of all chars in all words)
- *
- * Space Complexity: O(words.length)
- */
- class Solution {
- class Word {
- String word;
- int index;
- Word(String w) {
- word = w;
- index = 0;
- }
- }
- public int numMatchingSubseq(String S, String[] words) {
- if (S == null || words == null || S.length() == 0 || words.length == 0) {
- return 0;
- }
- Map<Character, List<Word>> map = new HashMap();
- for (String word : words) {
- if (word.length() > S.length()) {
- continue;
- }
- char c = word.charAt(0);
- if (!map.containsKey(c)) {
- map.put(c, new ArrayList<Word>());
- }
- map.get(c).add(new Word(word));
- }
- int result = 0;
- for (char c : S.toCharArray()) {
- if (!map.containsKey(c)) {
- continue;
- }
- List<Word> curBucket = map.get(c);
- map.put(c, new ArrayList<Word>());
- // Overall this for loop will run for summation of all chars in all words.
- for (Word w : curBucket) {
- w.index++;
- if (w.word.length() == w.index) {
- result++;
- } else {
- char nextChar = w.word.charAt(w.index);
- if (!map.containsKey(nextChar)) {
- map.put(nextChar, new ArrayList<Word>());
- }
- map.get(nextChar).add(w);
- }
- }
- curBucket.clear();
- }
- return result;
- }
- }
- /*
- * Using Solution of https://leetcode.com/problems/is-subsequence
- *
- * Pre Processing Time = O(S.length())
- *
- * Time Complexity: O(Sum of all word lengths * log S)
- *
- * Space Complexity: O(S)
- */
- class Solution {
- public int numMatchingSubseq(String S, String[] words) {
- if (S == null || words == null || S.length() == 0 || words.length == 0) {
- return 0;
- }
- Map<Character, List<Integer>> map = processStr(S);
- int result = 0;
- for (String word : words) {
- if (word.length() > S.length()) {
- continue;
- }
- if (isSubsequence(map, word)) {
- result++;
- }
- }
- return result;
- }
- private Map<Character, List<Integer>> processStr(String s) {
- Map<Character, List<Integer>> map = new HashMap();
- for (int i = 0; i < s.length(); i++) {
- char c = s.charAt(i);
- if (!map.containsKey(c)) {
- map.put(c, new ArrayList<Integer>());
- }
- map.get(c).add(i);
- }
- return map;
- }
- private boolean isSubsequence(Map<Character, List<Integer>> map, String s) {
- int prevIdx = -1;
- for (char c : s.toCharArray()) {
- if (!map.containsKey(c)) {
- return false;
- }
- int nextIdx = binarySearchInList(map.get(c), prevIdx);
- if (nextIdx == -1) {
- return false;
- }
- prevIdx = nextIdx;
- }
- return true;
- }
- private int binarySearchInList(List<Integer> list, int prev) {
- int start = 0;
- int end = list.size() - 1;
- while (start < end) {
- int mid = start + (end - start) / 2;
- if (list.get(mid) <= prev) {
- start = mid + 1;
- } else {
- end = mid;
- }
- }
- return list.get(start) > prev ? list.get(start) : -1;
- }
- }
Add Comment
Please, Sign In to add comment