LeetCode题练习与总结：键盘行--500

一、题目描述

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

请注意，字符串 不区分大小写，相同字母的大小写形式都被视为在同一行。

美式键盘 中：

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

American keyboard

示例 1：

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

输出：["Alaska","Dad"]

解释：

由于不区分大小写，"a" 和 "A" 都在美式键盘的第二行。

示例 2：

输入：words = ["omk"]

输出：[]

示例 3：

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

输出：["adsdf","sfd"]

提示：

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

二、解题思路

创建三个字符串变量，分别表示键盘的三行字符。
遍历输入的字符串数组 words。
对于每个单词，将其转换为小写（或大写），以便统一处理。
检查单词中的每个字符是否都在同一行键盘上。具体做法是，对于单词中的每个字符，检查它是否在键盘的第一行字符中，第二行字符中，还是第三行字符中。一旦确定某个字符属于某一行，后续字符也必须在这一行中，否则该单词不符合条件。
如果单词中的所有字符都在同一行键盘上，将该单词添加到结果列表中。
返回结果列表。

三、具体代码

import java.util.ArrayList;
import java.util.List;class Solution {public String[] findWords(String[] words) {// 定义键盘三行的字符String row1 = "qwertyuiop";String row2 = "asdfghjkl";String row3 = "zxcvbnm";// 创建一个列表来存储符合条件的单词List<String> result = new ArrayList<>();// 遍历每个单词for (String word : words) {// 将单词转换为小写String lowerWord = word.toLowerCase();// 初始化一个标志，用来判断单词是否在某一行的键盘上boolean inRow1 = row1.contains(String.valueOf(lowerWord.charAt(0)));boolean inRow2 = row2.contains(String.valueOf(lowerWord.charAt(0)));boolean inRow3 = row3.contains(String.valueOf(lowerWord.charAt(0)));// 检查单词中的每个字符是否都在同一行boolean isSameRow = true;for (char c : lowerWord.toCharArray()) {if ((inRow1 && !row1.contains(String.valueOf(c))) ||(inRow2 && !row2.contains(String.valueOf(c))) ||(inRow3 && !row3.contains(String.valueOf(c)))) {isSameRow = false;break;}}// 如果单词中的所有字符都在同一行，则添加到结果列表中if (isSameRow) {result.add(word);}}// 将结果列表转换为数组并返回return result.toArray(new String[0]);}
}

这段代码首先定义了键盘三行的字符，然后遍历输入的单词数组，将每个单词转换为小写，并检查是否所有字符都在同一行键盘上。如果符合条件，则将该单词添加到结果列表中。最后，将结果列表转换为数组并返回。

四、时间复杂度和空间复杂度

1. 时间复杂度

假设 words 数组中有 n 个单词。
对于每个单词，我们首先将其转换为小写，这需要 O(m) 的时间复杂度，其中 m 是单词的长度。
接着，我们检查单词中的每个字符是否都在同一行键盘上，这需要遍历单词中的每个字符，因此需要 O(m) 的时间复杂度。
由于我们需要对每个单词都进行这样的操作，因此总的时间复杂度是 O(n * m)，其中 n 是单词的数量，m 是单词的平均长度。

综上所述，时间复杂度是 O(n * m)。

2. 空间复杂度

我们定义了三个字符串变量 row1, row2, row3 来存储键盘的行字符，这些字符串的长度是固定的，因此它们的空间复杂度是 O(1)。
我们创建了一个列表 result 来存储符合条件的单词。在最坏的情况下，如果所有单词都符合条件，那么 result 的大小将与 words 相同，因此空间复杂度是 O(n)。
在检查单词时，我们使用了 lowerWord 字符串来存储小写的单词，这需要 O(m) 的空间，其中 m 是单词的长度。
由于 lowerWord 在每次循环时都会被重新定义，因此我们不需要将其计入总空间复杂度。

综上所述，空间复杂度是 O(n)，其中 n 是输入数组 words 的大小。注意，虽然检查单词时使用了 O(m) 的空间，但由于这是在每次循环中临时使用的，所以它不影响总的空间复杂度。

五、总结知识点

类定义：定义了一个名为 Solution 的类，这是面向对象编程的基础。
方法定义：在类中定义了一个公共方法 findWords，它接受一个字符串数组 words 作为参数并返回一个字符串数组。
字符串操作：
- 使用 toLowerCase() 方法将字符串转换为小写，以便统一处理不区分大小写的字符。
- 使用 contains() 方法检查一个字符串是否包含特定的字符。
字符操作：
- 使用 char 类型来表示单个字符。
- 使用 String.valueOf(char c) 将 char 类型转换为 String 类型。
循环和条件判断：
- 使用 for 循环遍历字符串数组 words 和字符串中的每个字符。
- 使用 if 语句和逻辑运算符进行条件判断。
逻辑控制：
- 使用布尔变量 isSameRow 来标记单词中的所有字符是否都在同一行键盘上。
- 使用 break 语句在满足特定条件时退出循环。
数据结构：
- 使用 ArrayList 来存储符合条件的单词。
- 使用 List 接口来定义 result 变量，这是泛型编程的体现。
数组与列表的转换：
- 使用 toArray(new String[0]) 方法将 ArrayList 转换为数组。
常量字符串：定义了三个常量字符串 row1, row2, row3 来表示键盘的每一行字符。
变量作用域：在 for 循环内部定义的变量 lowerWord, inRow1, inRow2, inRow3, isSameRow 仅在循环内部有效。