Java实现 LeetCode 792 自定义字符串排序（暴力）

系统管理员 2023-05-21 06:00 16阅读 0赞

## 792. 匹配子序列的单词数 ##

给定字符串 S 和单词字典 words, 求 words\[i\] 中是 S 的子序列的单词个数。

示例:  
输入:  
S = “abcde”  
words = \[“a”, “bb”, “acd”, “ace”\]  
输出: 3  
解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。  
注意:

所有在words和 S 里的单词都只由小写字母组成。  
S 的长度在 \[1, 50000\]。  
words 的长度在 \[1, 5000\]。  
words\[i\]的长度在\[1, 50\]。

class Solution { 
        public int numMatchingSubseq(String S, String[] words) { 
            int n = words.length;
            LinkedList<Integer>[] l = new LinkedList[26];
            int [] left = new int [n];
            for(int i = 0; i < 26; i++)
                l[i] = new LinkedList();
    
            //把每一个单词的开头第一个字母的索引放进list数组里面
            for(int j = 0; j < n; j++)
            { 
                left[j] = words[j].length();
                int p = (int)(words[j].charAt(0) - 'a');
                l[p].addLast(j);
            }
    
            for(int k = 0; k < S.length(); k++)
            { 
                //找到当前开头的
                int cur = (int)(S.charAt(k) - 'a');
                int clen = l[cur].size();
                for(int x = 0; x < clen; x++)
                { 
                    //这个是以当前字母开头的字符串的索引
                    int q = l[cur].pollFirst();
                    left[q] --;
                    if(left[q] > 0)
                    { 
                        //当前的字母改完了之后，，就找这个单词的下一个字符
                        int p = (int)(words[q].charAt(words[q].length() - left[q]) - 'a');
                        l[p].addLast(q);
                    }
    
                }
            }
            //到最后，把所有=0的拿出来，=0就是因为全都拿出来了
            int sum = 0;
            for(int j = 0; j < n; j++)
                if(left[j] == 0)
                    sum ++;
    
            return sum;
        }
    }