字符串变换最小字符串

题目

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。 变换规则：交换字符串中任意两个不同位置的字符。

输入描述：
一串小写字母组成的字符串s

输出描述：
按照要求进行变换得到的最小字符串

示例

输入：abcdef 
输出：abcdef 
说明：abcdef已经是最小字符串，不需要交换 

输入：bcdefa 
输出：acdefb 
说明：a和b进行位置交换，可以得到最小字符串

备注：
s是都是小写字符组成
1<=s.length<=1000

思路

贪心策略

• 根本不需要每个都穷举出来进行比对
• 对于一个字符串,只需要把字符串中最小字符调换位置到第一位就是最小字符串
• 如果第一个字符已经是最小字符,则对除去第一个字符的字串进行操作
  所以我就直接用递归进行操作

注意

如果最小字符有多个,记得取最后一个最小字符,不然会有很多用例通不过

代码

import java.util.Scanner;


public class Main1 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String inputString = in.next();
		
        char[] chars = inputString.toCharArray();

        moveTheSmallest2Head(chars, 0);

        System.out.println(new String(chars));
    }

    private static void moveTheSmallest2Head(char[] chars, int start) {

        if (start == chars.length - 1) {
            return;
        }

        boolean headIsSmallest = true;


        char smallest = chars[start];
        int samallestIndex = start;

        for (int i = start + 1; i < chars.length; i++) {
            if (chars[i] < chars[start] && chars[i] <= smallest) {
                headIsSmallest = false;
                smallest = chars[i];
                samallestIndex = i;
            }
        }

        if (headIsSmallest) {
            moveTheSmallest2Head(chars, start + 1);
        } else {
            char temp = chars[start];
            chars[start] = chars[samallestIndex];
            chars[samallestIndex] = temp;
        }
    }
}