算法-贪心-拼接字符得到最小字典序

2022-4-18 diaba 算法

package com.jiucaiyuan.net.question;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 【问题】一个数组中很多字符串，怎么拼接一起得到字典序最小？
 * 【思路】字符串a和b，如果a+b字典序小于b+a，则拼接方法是a+b得到小的字典序
 *
 * @Author jiucaiyuan  2022/4/18 22:49
 * @mail services@jiucaiyuan.net
 */

public class LowestLexicography {
    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String s1, String s2) {
            return (s1 + s2).compareTo(s2 + s1);
        }
    }

    public static String lowestString(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String result = "";
        for (int i = 0; i < strs.length; i++) {
            result += strs[i];
        }
        return result;
    }

    public static void main(String[] args) {
        String[] strs = {"an", "zs", "eds", "abc", "aa"};
        System.out.println(lowestString(strs));
    }
}

« 算法-贪心-成本最小切金条 | 算法-前缀树（单词查找树）»

发表评论：