• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
• This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode – 500 – keyboard line

[Blog link]

The path to learning at

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

You are given a string array of words that returns only words that can be printed using letters on the same line on an American keyboard. The keyboard is shown below.

In American keyboards:

The first line consists of the character “qWERtyuiop”. The second line consists of the character “asDFghjkl”. The third line consists of the character “ZXCVBNM”.

Example 1:

Input: words = [" Hello ", "Alaska", "Dad", "Peace"] output: [" Alaska ", "Dad"]Copy the code

Example 2:

Input: words = ["omk"] Output: []Copy the code

Example 3:

Words = ["adsdf"," SFD "] output: ["adsdf"," SFD "]Copy the code

Tip:

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• Words [I] consists of lowercase and uppercase letters

Idea 1: violent search

• Inch 26 letters
• And then it’s a simple simulation

class Solution {
        public String[] findWords(String[] words) {
            List<String> list = new ArrayList<>();
            Set<Character> set1 = new HashSet<>();
            Set<Character> set2 = new HashSet<>();
            Set<Character> set3 = new HashSet<>();
            set1.add('q');
            set1.add('w');
            set1.add('e');
            set1.add('r');
            set1.add('t');
            set1.add('y');
            set1.add('u');
            set1.add('i');
            set1.add('o');
            set1.add('p');
            set2.add('a');
            set2.add('s');
            set2.add('d');
            set2.add('f');
            set2.add('g');
            set2.add('h');
            set2.add('j');
            set2.add('k');
            set2.add('l');
            set3.add('z');
            set3.add('x');
            set3.add('c');
            set3.add('v');
            set3.add('b');
            set3.add('n');
            set3.add('m');
            for (String word : words
            ) {
                Set<Character> set = new HashSet<>();
                if (set1.contains(Character.toLowerCase(word.charAt(0)))) {
                    set = set1;
                }
                if (set2.contains(Character.toLowerCase(word.charAt(0)))) {
                    set = set2;
                }
                if (set3.contains(Character.toLowerCase(word.charAt(0)))) {
                    set = set3;
                }
                boolean flag = true;
                for (Character c : word.toCharArray()
                ) {
                    if(! set.contains(Character.toLowerCase(c))) { flag =false; }}if(flag) { list.add(word); }}return list.toArray(new String[0]); }}Copy the code

• Time complexity O(
  $\sum_{i=0}^{n}{words[i].length}$)
• Space complexity O(1)