Welcome to Subscribe On Youtube

500. Keyboard Row

Description

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

In the American keyboard:

• the first row consists of the characters "qwertyuiop",
• the second row consists of the characters "asdfghjkl", and
• the third row consists of the characters "zxcvbnm".

 

Example 1:

Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]

Example 2:

Input: words = ["omk"]
Output: []

Example 3:

Input: words = ["adsdf","sfd"]
Output: ["adsdf","sfd"]

 

Constraints:

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words[i] consists of English letters (both lowercase and uppercase). 

Solutions

Solution 1: Set

We map the characters of each keyboard row to the corresponding row number, and then traverse the string array to determine whether each string is on the same row.

Time complexity $O(L)$, space complexity $O(C)$. Among them, $L$ is the sum of the lengths of all strings; and $C$ is the size of the character set, in this question $C = 26$.

Solution 2

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• C#

• class Solution {
      public String[] findWords(String[] words) {
          String s = "12210111011122000010020202";
          List<String> ans = new ArrayList<>();
          for (var w : words) {
              String t = w.toLowerCase();
              char x = s.charAt(t.charAt(0) - 'a');
              boolean ok = true;
              for (char c : t.toCharArray()) {
                  if (s.charAt(c - 'a') != x) {
                      ok = false;
                      break;
                  }
              }
              if (ok) {
                  ans.add(w);
              }
          }
          return ans.toArray(new String[0]);
      }
  }
  

• class Solution {
  public:
      vector<string> findWords(vector<string>& words) {
          string s = "12210111011122000010020202";
          vector<string> ans;
          for (auto& w : words) {
              char x = s[tolower(w[0]) - 'a'];
              bool ok = true;
              for (char& c : w) {
                  if (s[tolower(c) - 'a'] != x) {
                      ok = false;
                      break;
                  }
              }
              if (ok) {
                  ans.emplace_back(w);
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def findWords(self, words: List[str]) -> List[str]:
          ans = []
          s = "12210111011122000010020202"
          for w in words:
              x = s[ord(w[0].lower()) - ord('a')]
              if all(s[ord(c.lower()) - ord('a')] == x for c in w):
                  ans.append(w)
          return ans
  
  
  # Solution 2
  class Solution:
      def findWords(self, words: List[str]) -> List[str]:
          ans = []
          s = "12210111011122000010020202"
          for w in words:
              x = s[ord(w[0].lower()) - ord('a')]
              if all(s[ord(c.lower()) - ord('a')] == x for c in w):
                  ans.append(w)
          return ans
  
  

• func findWords(words []string) (ans []string) {
  	s := "12210111011122000010020202"
  	for _, w := range words {
  		x := s[unicode.ToLower(rune(w[0]))-'a']
  		ok := true
  		for _, c := range w[1:] {
  			if s[unicode.ToLower(c)-'a'] != x {
  				ok = false
  				break
  			}
  		}
  		if ok {
  			ans = append(ans, w)
  		}
  	}
  	return
  }
  

• function findWords(words: string[]): string[] {
      const s = '12210111011122000010020202';
      const ans: string[] = [];
      for (const w of words) {
          const t = w.toLowerCase();
          const x = s[t.charCodeAt(0) - 'a'.charCodeAt(0)];
          let ok = true;
          for (const c of t) {
              if (s[c.charCodeAt(0) - 'a'.charCodeAt(0)] !== x) {
                  ok = false;
                  break;
              }
          }
          if (ok) {
              ans.push(w);
          }
      }
      return ans;
  }
  
  

• public class Solution {
      public string[] FindWords(string[] words) {
          string s = "12210111011122000010020202";
          IList<string> ans = new List<string>();
          foreach (string w in words) {
              char x = s[char.ToLower(w[0]) - 'a'];
              bool ok = true;
              for (int i = 1; i < w.Length; ++i) {
                  if (s[char.ToLower(w[i]) - 'a'] != x) {
                      ok = false;
                      break;
                  }
              }
              if (ok) {
                  ans.Add(w);
              }
          }
          return ans.ToArray();
      }
  }
  

All Problems

All Solutions