LeetCode 1451. 重新排列句子中的单词

Categories:

题目描述
思路分析
1. 解法一：稳定排序（推荐）
相似题目

题目描述

✅ 1451. 重新排列句子中的单词

思路分析

解法一：稳定排序（推荐）

核心思路：

将句子转为小写后按单词长度稳定排序。

最终把第一个单词首字母大写。

复杂度分析：

时间复杂度：O(n log n)，n 为单词数量。

空间复杂度：O(n)。

import java.util.Arrays;

class Solution {
    public String arrangeWords(String text) {
        String[] words = text.toLowerCase().split(" ");
        Arrays.sort(words, (a, b) -> {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            return 0;
        });

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(words[i]);
        }

        sb.setCharAt(0, Character.toUpperCase(sb.charAt(0)));
        return sb.toString();
    }
}

import "sort"

func arrangeWords(text string) string {
    words := splitWords(text)
    for i := range words {
        words[i] = toLower(words[i])
    }

    sort.SliceStable(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })

    if len(words) == 0 {
        return ""
    }

    words[0] = capitalize(words[0])
    return joinWords(words)
}

func splitWords(s string) []string {
    res := make([]string, 0)
    cur := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            if len(cur) > 0 {
                res = append(res, string(cur))
                cur = cur[:0]
            }
        } else {
            cur = append(cur, s[i])
        }
    }
    if len(cur) > 0 {
        res = append(res, string(cur))
    }
    return res
}

func joinWords(words []string) string {
    if len(words) == 0 {
        return ""
    }
    total := 0
    for _, w := range words {
        total += len(w)
    }
    buf := make([]byte, 0, total+len(words)-1)
    for i, w := range words {
        if i > 0 {
            buf = append(buf, ' ')
        }
        buf = append(buf, []byte(w)...)
    }
    return string(buf)
}

func toLower(s string) string {
    b := []byte(s)
    for i := 0; i < len(b); i++ {
        if b[i] >= 'A' && b[i] <= 'Z' {
            b[i] = b[i] - 'A' + 'a'
        }
    }
    return string(b)
}

func capitalize(s string) string {
    if len(s) == 0 {
        return s
    }
    b := []byte(s)
    if b[0] >= 'a' && b[0] <= 'z' {
        b[0] = b[0] - 'a' + 'A'
    }
    return string(b)
}

相似题目

题目	难度	考察点
1859. 将句子排序	简单	排序
937. 重新排列日志文件	中等	排序
151. 反转字符串中的单词	中等	字符串
186. 反转字符串中的单词 II	中等	字符串
58. 最后一个单词的长度	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/48208682