Question

500. 键盘行

English Version

题目描述

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

• 第一行由字符 "qwertyuiop" 组成。
• 第二行由字符 "asdfghjkl" 组成。
• 第三行由字符 "zxcvbnm" 组成。

 

示例 1：

输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]

示例 2：

输入：words = ["omk"]
输出：[]

示例 3：

输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

 

提示：

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words[i] 由英文字母（小写和大写字母）组成

解法

方法一：字符映射

我们将每个键盘行的字符映射到对应的行数，然后遍历字符串数组，判断每个字符串是否都在同一行即可。

时间复杂度 $O(L)$，空间复杂度 $O(C)$。其中 $L$ 为所有字符串的长度之和；而 $C$ 为字符集的大小，本题中 $C = 26$。

class Solution:
  def findWords(self, words: List[str]) -> List[str]:
    s1 = set('qwertyuiop')
    s2 = set('asdfghjkl')
    s3 = set('zxcvbnm')
    ans = []
    for w in words:
      s = set(w.lower())
      if s <= s1 or s <= s2 or s <= s3:
        ans.append(w)
    return ans

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;
  }
};

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();
  }
}

方法二

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