IsSubsequence392

[underwindfall]

• https://leetcode-cn.com/problems/is-subsequence/

• 思路

  • double index
  • hashmap + bineary search

• [x] 刷15mins

• [x] 刷5mins

// 思路双指针比较两个字符串的，
    // 如果s字符串的index等于i遍历的值那就是说是子集
    class DoubleIndex {
        public boolean isSubsequence(String s, String t) {
            // 双指针解法
            int i = 0, j = 0;
            while (i < s.length() && j < t.length()) {
                char si = s.charAt(i);
                char tj = t.charAt(j);
                if (si == tj) {
                    i++;
                }
                j++;
            }
            return i == s.length();
        }
    }

   public boolean isSubsequence(String s, String t) {
        //t index
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<>());
            }
            map.get(c).add(i);
        }

        //O(k * s * logT)
        //aaabbcc
        //a 0, 1,2
        //b 3,4
        //c 5,6
        //s1, s2 //aabc
        //for s
        //index
        int prev = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.get(c) == null) {
                return false;
            } else {
                List<Integer> list = map.get(c); //a 0,1,2 // sort order 
                //binary search(a, b,c) // leftmost
                //a,b,c
                //a = list.get(index)
                //prev = list.get(index) + 1;
                int index = binarySearch(prev, list, 0, list.size() - 1);
                if (list.get(index) < prev) {
                    return false;
                } else {
                    prev = list.get(index) + 1;      
                }
            }
        }
        return true;
    }

    //O(logT)
    //leftmost
    int binarySearch(int index, List<Integer> list, int left, int right) {
        while (left < right) {
            //lower bound
            int mid = (right - left)/ 2 + left;
            if (list.get(mid) < index) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

       return left;
    }