3216.交换后字典序最小的字符串

【LetMeFly】3216.交换后字典序最小的字符串：贪心(模拟)

力扣题目链接：https://leetcode.cn/problems/lexicographically-smallest-string-after-a-swap/

给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。

如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。

 

示例 1：

输入： s = "45320"

输出： "43520"

解释：

s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。

示例 2：

输入： s = "001"

输出： "001"

解释：

无需进行交换，因为 s 已经是字典序最小的。

 

提示：

• 2 <= s.length <= 100
• s 仅由数字组成。

解题方法：贪心

想要字符串字典序尽可能小，那是自然是越靠前的字符越小越好。

也就是说，前面字符能变小的话(哪怕只能变小一丢丢)，不论后面字符能变小多少，就一定还是变小前面的而不变后面的。

因此只需要从前到后遍历字符串，如果相邻两个字符串满足交换规则且前面字符串大于后面字符串，就交换二者并返回。

• 时间复杂度$O(len(s))$
• 空间复杂度：对于可变字符串的编程语言如C++，$O(1)$；对于不可变字符串的编程语言如Python、Go、Java，$O(n)$

AC代码

C++

class Solution {
public:
    string getSmallestString(string s) {
        for (int i = 1; i < s.size(); i++) {
            if (s[i - 1] > s[i] && s[i - 1] % 2 == s[i] % 2) {
                swap(s[i - 1], s[i]);
                return s;
            }
        }
        return s;
    }
};

Python

class Solution:
    def getSmallestString(self, s: str) -> str:
        temp = list(s)
        for i in range(1, len(s)):
            if ord(temp[i - 1]) > ord(temp[i]) and ord(temp[i - 1]) % 2 == ord(temp[i]) % 2:
                temp[i - 1], temp[i] = temp[i], temp[i - 1]
                break
        return ''.join(temp)

Go

package main

func getSmallestString(s string) string {
    temp := []byte(s)
    for i := 1; i < len(s); i++ {
        if s[i - 1] > s[i] && s[i - 1] % 2 == s[i] % 2 {
            temp[i - 1], temp[i] = s[i], s[i - 1]
            return string(temp)
        }
    }
    return s
}

Java

class Solution {
    public String getSmallestString(String s) {
        char[] tempS = s.toCharArray();
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i - 1) > s.charAt(i) && s.charAt(i - 1) % 2 == s.charAt(i) % 2) {
                char temp = s.charAt(i);
                tempS[i] = tempS[i - 1];
                tempS[i - 1] = temp;
                // return tempS.toString();  // 不可，不然"45320"会变成"[C@5010be6"
                return new String(tempS);
            }
        }
        return s;
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143362223