LeetCode算法题-Keyboard Row(Java实现)

作者 : 开心源码 本文共2138个字,预计阅读时间需要6分钟 发布时间: 2022-05-12 共261人阅读

这是悦乐书的第245次升级,第258篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第112题(顺位题号是500)。给定一个单词列表,返回可以在美国键盘的一行上使用字母表键入的单词,如下图所示。

image

例如:

输入:[“Hello”,”Alaska”,”Dad”,”Peace”]

输出:[“Alaska”,”Dad”]

注意:

  • 您可以屡次使用键盘中的一个字符。

  • 您可以假设输入字符串仅包含字母。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

题目的意思是从一个字符串数组中找出只由某一行字母(有3行字母)组成的字符串,并且作为字符串数组输出。

对此,我们可以将每一行的字母作为key,行号为value,存入HashMap中。而后我们遍历字符串数组中的元素,获取到当前字符串,得到其第一个字符所在行号,而后依次判断剩下字符所在行号,假如和第一个字符所在行号不相等,就将行号重新赋值,假如遍历完剩下的字符行号不变,就将其增加进list中,最后将list转为字符串数组作为结果输出。

public String[] findWords(String[] words) {    List<String> list = new ArrayList<String>();    Map<Character, Integer> map = new HashMap<Character, Integer>();    String s1 = "qwertyuiopQWERTYUIOP";    String s2 = "asdfghjklASDFGHJKL";    String s3 = "zxcvbnmZXCVBNM";    for (char ch : s1.toCharArray()) {        map.put(ch, 1);    }    for (char ch : s2.toCharArray()) {        map.put(ch, 2);    }    for (char ch : s3.toCharArray()) {        map.put(ch, 3);    }    for (int i=0; i<words.length; i++) {        String ss = words[i];        int floor = map.get(ss.charAt(0));        for (char ch : ss.toCharArray()) {            if (floor != map.get(ch)) {                floor = map.get(ch);                break;            }        }        if (floor == map.get(ss.charAt(0))) {            list.add(ss);        }    }    return list.toArray(new String[list.size()]);}

03 第二种解法

针对第一种解法,我们可以使用数组进行替代,这样更轻便少量。

仍旧是那三行字符组成的字符串,存入一个数组中,而后遍历words中的元素,拿到当前字符串后,借助一个额外的方法getRowNum来获取某一字符所在的行号,而后判断该字符串剩下的字符,能否仍旧存在于该行号所在字符串中,全都存在就将其增加进list中,最后将其转为字符串数组作为结果输出。

private String[] keyString = {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};public String[] findWords2(String[] words) {    List<String> list = new ArrayList<String>();    for (int i=0; i<words.length; i++) {        int currentRow = getRowNum(words[i].charAt(0));        boolean flag = true;        for (char ch : words[i].toCharArray()) {            if (keyString[currentRow].indexOf(ch) == -1) {                flag = false;            }        }        if (flag) {            list.add(words[i]);        }    }    return list.toArray(new String[list.size()]);}public int getRowNum (char ch) {    for (int i=0; i<keyString.length; i++) {        if (keyString[i].indexOf(ch) != -1) {            return i;        }    }    return -1;}

04 第三种解法

还有更加疯狂的解法,一行代码搞定。

public String[] findWords3(String[] words) {        return Stream.of(words).filter(s -> s.toLowerCase().matches("[qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*")).toArray(String[]::new);    }

05 小结

算法专题目前已日更超过三个月,算法题文章112+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Keyboard Row(Java实现)

发表回复