LeetCode（Map)1684. Count the Number of Consistent Strings

墨蓝 2023-09-24 16:39 133阅读 0赞

# 1.问题 #

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

> Input: allowed = “ab”, words = \[“ad”,“bd”,“aaab”,“baa”,“badab”\]  
> Output: 2  
> Explanation: Strings “aaab” and “baa” are consistent since they only contain characters ‘a’ and ‘b’.

Example 2:

> Input: allowed = “abc”, words = \[“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”\]  
> Output: 7  
> Explanation: All strings are consistent.

Example 3:

> Input: allowed = “cad”, words = \[“cc”,“acd”,“b”,“ba”,“bac”,“bad”,“ac”,“d”\]  
> Output: 4  
> Explanation: Strings “cc”, “acd”, “ac”, and “d” are consistent.

Constraints:

*  1 <= words.length <= 104
 *  1 <= allowed.length <= 26
 *  1 <= words\[i\].length <= 10  
    The characters in allowed are distinct.  
    words\[i\] and allowed contain only lowercase English letters.

# 2. 解题思路 #

## 方法1： ##

> 1.定义result初始为0  
> 2.for循环遍历words，如果allowed包含words中char数组元素为ture，result+1，否者为false，result不变  
> 3.返回result

## 方法2： ##

> 1.定义result初始为0  
> 2.新建一个hashset,将allowed.toCharArray()存入set中  
> 3.for循环遍历words，如果set包含words中char数组元素为ture，result+1，否者为false，result不变  
> 4.返回result

## 方法3： ##

> 1.定义长度为26的数组  
> 2.for循环遍历，ch-'a’是元素在alpha数组的位置  
> 3.遍历words的char数组元素，alpha\[ch-‘a’\]是元素在alpha中的位置，<=0是没有出现在数组中，T:继续循环，直到出现+1  
> 4.返回count

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int countConsistentStrings(String allowed, String[] words) {
        
            int result =0;//1.定义result初始为0
            for(String w:words){
        //2.for循环遍历words，如果allowed包含words中char数组元素为ture，result+1，否者为false，result不变
                boolean flag = true;
                for(char c: w.toCharArray()){
        
                    if(!allowed.contains(String.valueOf(c))){
        
                        flag=false;
                    }
    
                }
                if(flag) result+=1;
            }
            return result;//3.返回result
        }
    }

## 代码2： ##

class Solution {
        
        public int countConsistentStrings(String allowed, String[] words) {
        
            int result =0;//1.定义result初始为0
            Set<Character> set = new HashSet<>();//2.新建一个hashset,将allowed.toCharArray()存入set中
            for(char a: allowed.toCharArray()){
        
                set.add(a);
            }
            for(String w:words){
        //3.for循环遍历words，如果set包含words中char数组元素为ture，result+1，否者为false，result不变
                boolean flag = true;
                for(char c: w.toCharArray()){
        
                    if(!set.contains(c)){
        //注意：这是set.contains(c)是charter.contains(charter)
                        flag=false;
                    }
                }
                if(flag) result+=1;
            }
            return result;//4.返回result
        }
    }

## 方法3： ##

class Solution {
        
        public int countConsistentStrings(String allowed, String[] words) {
        
            int [] alpha = new int[26];//1.定义长度为26的数组
            for (int i=0; i < allowed.length(); i++)//2.for循环遍历，ch-'a'是元素在alpha数组的位置
            {
        
                char ch = allowed.charAt(i);
                alpha[ch-'a']++;
            }
    
            int count = 0;
    
            T: for (String word : words){
        //3.遍历words的char数组元素，alpha[ch-'a']是元素在alpha中的位置，<=0是没有出现在数组中，T:继续循环，直到出现+1
                for ( char ch:word.toCharArray()) {
        
                    if (alpha[ch-'a'] <= 0) continue T;
                }
                count++;
            }
    
    //
            return count;//4.返回count
        }
    }

> 解题思路基本相同，不同的地方在于查询方式后结果+1；相比上面代码下面的代码比较容易理解

class Solution {
        
        public int countConsistentStrings(String allowed, String[] words) {
        
            boolean alph[]=new boolean[26];//1.新建boolenan的数组
            for(char c:allowed.toCharArray()){
        //2.如果allow的char元素在a数组元素中，为true
                alph[c-'a']=true;
            }
            int count=0;
            for(String i:words){
        //3.for循环遍历words，a[c-'a']是元素是否在alph中，如果alph[c-'a']为ture，result+1，否者为false，result不变
                boolean flag=true;
                for(char c:i.toCharArray()){
        
                    if(!alph[c-'a']){
        
                        flag=false;
                    }
                }
                if(flag){
        
                    count++;
                }
            }
            return count;//4.返回count
        }
    }