【华为OD机试真题2023C&D卷Python&C++】字符串变换最小字符串

?华为OD2023（C&D卷）机试题库全覆盖，刷题指南点这里

字符串变换最小字符串

知识点字符串

时间限制：1s?空间限制：256MB?限定语言：不限

题目描述：

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。

变换规则：交换字符串中任意两个不同位置的字符。

?
输入描述：

一串小写字母组成的字符串s

输出描述：

按照要求进行变换得到的最小字符串

补充说明：

s是都是小写字符组成

1<=s.length<=1000

示例1

输入：

abcdef

输出：

abcdef

说明：

abcdef已经是最小字符串，不需要交换

示例2

输入：

bcdefa

输出：

acdefb

说明：

a和b进行位置交换，可以等到最小字符串

解题思路：

这个跟冒泡算法差不多，就是相邻两个进行比较，进行两两交换，将较小的字符放在前面

代码（Python）：?

import sys

for line in sys.stdin:
    s = line.strip()
    res = s
    n = len(s)
    for i in range(n):
        for j in range(i+1, n):
            c = list(s)
            t = c[i]
            c[i] = c[j]
            c[j] = t
            s2 = "".join(c)
            if res > s2:
                res = s2
    print(res)

代码（C++）：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        string res = s;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                string c = s;
                char t = c[i];
                c[i] = c[j];
                c[j] = t;
                string s2 = c;
                if (res > s2) {
                    res = s2;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}