792. 匹配子序列的单词数

792. 匹配子序列的单词数

// 时间复杂度 n + m * k
    public int numMatchingSubseq(String s, String[] words) {
        List<List<Pair>> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) list.add(new ArrayList<>());
        // 初始化，把word的第一字母放进list里
        for (int i = 0; i < words.length; i++) list.get(words[i].charAt(0) - 'a').add(new Pair(i, 0));
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            List<Pair> temp = new ArrayList<>();
            // 把等于该字符的word的数据下标往后移
            List<Pair> chars = list.get(s.charAt(i) - 'a');
            for (Pair pair : chars) {
                // 如果该word的下标下一位等于该word 的长度 则说明已经走完了
                if (pair.y + 1 == words[pair.x].length()) res++;
                else temp.add(new Pair(pair.x, pair.y + 1));
            }
            chars.clear();
            // 在相应的字符list中 add  相应word的下一位
            for (Pair pair : temp) list.get(words[pair.x].charAt(pair.y) - 'a').add(pair);
        }
        return res;
    }


    static class Pair {
        // 第x个单词
        int x;
        // 第x个单词的第y个字符
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }