题解 | #字符串变形#

算法思想一：分块变形

解题思路：

主要是通过将字符串以空格分割开为字符串数组，然后对数组进行倒序遍历，在遍历过程对字符串进行大小写变换

1、初始化返回字符串result，字符串分割为数组： $slist = s.split(' ')$

2、倒序遍历 i:

1、当 i != 0 时，对字符串进行大小写变换，在字符串后需要加空格连接

2、当 i == 0 时，对字符串进行大小写变换，不需要在字符串后需要加空格连接

3、返回result

图解：

代码展示：

Python版本

# -*- coding:utf-8 -*-
class Solution:
    def trans(self, s, n):
        # write code here
        # 特殊情况
        if n == 0:
            return s
        # 返回字符
        result = ''
        # 将字符以空格分割开为字符数组
        slist = s.split(' ')
        # 对字符数字进行倒序遍历
        for i in range(len(slist)-1, -1, -1):
            tmp = slist[i]
            # 对每一个字符进行 swapcase 操作 再加上 ‘’ 空格
            # 字符串大小写转换
            if i != 0:
                result = result + tmp.swapcase() + ' '
            else:
                # 遍历到最后一个字符串时不需要再加空格
                result = result + tmp.swapcase()
        return result

复杂度分析

时间复杂度 $O(n)$ ：n表示字符串的长度，需要遍历一次字符串

空间复杂度 $O(n)$ ：对返回字符串的存储空间

算法思想二：遍历（超时）

解题思路：

方法二和方法一有同样的思想都是对字符串进行遍历，但是方法二是直接对字符串进行遍历，不需要分割

1、对字符串进行遍历

1、如果当前字符是小写字符，则转换为大写字符

2、如果当前字符是大写字符，则转换为小写字符

3、如果当前是空格，则需要增加一个空格字符

2、返回转换后的字符串

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    public String trans(String s, int n) {
        // write code here
        // 返回字符串
        String res = "";
        String tempStr = "";
        // 遍历字符串
        for(int i = 0; i < n; i++){
            char c = s.charAt(i);
            // 判断是否为字符
            if(c>='a'&& c<='z')
                // 小写字符转为大写
                tempStr += Character.toUpperCase(c);
            else if(c>='A'&& c<='Z')
                // 大写字符转为小写
                tempStr += Character.toLowerCase(c);
            else{
                // 空格字符
                tempStr = c+tempStr;
                res = tempStr + res;
                tempStr="";
            }
        }
        res = tempStr+res;
        return res;
    }
}

复杂度分析

时间复杂度 $O(n)$ ：n表示字符串的长度，需要遍历一次字符串

空间复杂度 $O(n)$ ：对返回字符串的存储空间

算法思想三：栈

解题思路：

首先读取单词，以空格为分界符（在字符串最后加上一个空格避免特判），读取的同时进行大小写转换，然后将单词加入到栈中。在全部单词读取完毕后，逐个弹出单词，即为答案

图解：

代码展示：

C++版本

class Solution {
public:
    string trans(string s, int n) {
        stack<string> sk;
        string str;
        s.push_back(' ');//避免特判
        for(int i = 0; i <= n; ++i) {//注意此时单词长度为n+1
            if(s[i] == ' ') {
                sk.push(str);//以空格为界进行压栈
                str = ""; 
            } else {
                if(s[i] >= 'a' && s[i] <= 'z') { 
                    str += (s[i] - 'a' + 'A'); 
                } else { 
                    str += (s[i] - 'A' + 'a'); 
                } 
            }
        } 
        string ans; 
        while(!sk.empty()) { 
            //从栈中逐个弹出单词 
            ans += sk.top(); sk.pop(); 
            ans.push_back(' '); 
        } 
        ans.pop_back();//去除最后一个单词后的空格 
        return ans;
    }
};

复杂度分析

时间复杂度 $O(n)$ ：n表示字符串的长度，需要遍历一次字符串

空间复杂度 $O(n)$ ：辅助栈空间