20天算法刷题计划-557. 反转字符串中的单词 III

简介: 根据题目分析, 使用额外的空间,将字符串放入数组中,遍历原有字符串,根据空格把字符串拆分成多个单词的字符串,我们只关心空格字符和最后一个字符,于是,遇到正常的字母字符一概不管;当找到空格时就找到了一个单词, 并将单词的字符串进行反转,然后继续找到下一个单词,最后 将反转的单词字符串拼接起来就是最终答案。

一、题目描述:

给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 1:
输入:s = "Let's take LeetCode contest"
输出:"s'teL ekat edoCteeL tsetnoc"
示例 2:
输入: s = "God Ding"
输出:"doG gniD"
提示:
1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少 有一个词。
s 中的所有单词都用一个空格隔开。

二、思路分析:

分析题目,注意点如下:

1.反转单词中字母顺序

2.保持原有单词顺序和空格

3.至少 有一个词

根据题目分析, 使用额外的空间,将字符串放入数组中,遍历原有字符串,根据空格把字符串拆分成多个单词的字符串,我们只关心空格字符和最后一个字符,于是,遇到正常的字母字符一概不管;当找到空格时就找到了一个单词, 并将单词的字符串进行反转,然后继续找到下一个单词,最后 将反转的单词字符串拼接起来就是最终答案。

三、AC 代码:

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        for (int i = 0; i < s.length(); i++) {    
            char currentChar = s.charAt(i);
            if (currentChar == ' ') {       
                reverse(chars, left, i - 1);          
                left = i + 1;
            } else if (i == s.length() - 1) {       
                reverse(chars, left, i);
            }
        }
        return String.valueOf(chars);
    }
     private static void reverse(char[] chars, int start, int end) {
        while (start < end) {
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            end --;
            start ++;
        }
    }
}

四、总结:

image-20220311093524880

执行结果通过了,但是看内存和执行用时并不是很高,应该还有很多更好的思路,可以多去看看大佬们的题解扩充下思路。



相关文章
|
3月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
1月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
63 1
两个字符串匹配出最长公共子序列算法
|
25天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
12 0
|
3月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
4月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
265 1
|
3月前
|
算法 容器
【算法】滑动窗口——串联所有单词的子串
【算法】滑动窗口——串联所有单词的子串
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
3月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
37 0
|
3月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
74 0
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。