LEETCODE 1451. Rearrange Words in a Sentence 解题思路分析

题目大意:

重新排列句子中的单词

「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :

  • 句子的首字母大写
  • text 中的每个单词都用单个空格分隔。

请你重新排列 text 中的单词,使所有单词按其长度的升序排列。如果两个单词的长度相同,则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

示例 1:

输入:text = "Leetcode is cool"
输出:"Is cool leetcode"
解释:句子中共有 3 个单词,长度为 8 的 "Leetcode" ,长度为 2 的 "is" 以及长度为 4 的 "cool" 。
输出需要按单词的长度升序排列,新句子中的第一个单词首字母需要大写。

示例 2:

输入:text = "Keep calm and code on"
输出:"On and keep calm code"
解释:输出的排序情况如下:
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母,因为存在长度相同的其他单词,所以它们之间需要保留在原句子中的相对顺序。
"calm" 4 个字母。
"code" 4 个字母。

示例 3:

输入:text = "To be or not to be"
输出:"To be or to be not"

提示:

  • text 以大写字母开头,然后包含若干小写字母以及单词间的单个空格。
  • 1 <= text.length <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1451

解题思路分析:

  1. 将字符串以空格分割成单词数组
  2. 将数组的首元素单词变换为小写
  3. 遍历数组每个单词,并使用一个HashMap统计出每种长度的单词列表。其中key为单词长度,value是长度为key的单词列表
  4. 按照HashMap中单词的长度依次取出每个单词列表,将单词以空格相连组成一个字符串,并将首字符改为大写。

实现代码:

public String arrangeWords(String text) {
    String[] arr=text.split(" ");  // 分割字符串
    arr[0]=arr[0].toLowerCase(); // 将首字符改为小写字母
     // 统计每种长度的单词列表
    Map<Integer, List<String>> map=new TreeMap<>();
    for(String s : arr){
        int length=s.length();
        List<String> list = map.getOrDefault(length,new ArrayList<>());
        list.add(s);
        map.put(length,list);
    }
    // 按照单词长度合并单词
    StringBuilder sb = new StringBuilder();
    for(int key : map.keySet()){
        List<String> list = map.get(key);
        if(list==null) continue;
        for(String s : list){
            if(sb.length()==0){ // 将首字符改为大写字母
                char[] cs=s.toCharArray();
                cs[0]-=32;
                s=String.valueOf(cs);
            }else{
                sb.append(" ");
            }
            sb.append(s);
        }
    }
    return sb.toString();
}

本题解法执行时间为15ms。

Runtime: 15 ms, faster than 100.00% of Java online submissions for Rearrange Words in a Sentence.

Memory Usage: 40.4 MB, less than 100.00% of Java online submissions for Rearrange Words in a Sentence.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1451-rearrange-words-in-a-sentence-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

LEETCODE 1451. Rearrange Words in a Sentence 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE周赛189 赛后总结及解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

电子邮件地址不会被公开。