描述

题目描述

给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串。

示例

输入：["abc","de"]
返回值："abcde"

知识点：字符串，数组
难度：⭐⭐⭐

题解

方法一：重载比较函数

解题思路：

算法流程：

• Java通过重写优先级队列PriorityQueue的比较器方法
• 保证 s1 + s2 > s2 + s1 时，返回值大于0，否则返回值小于0
• 同时保证queue中越靠近队头的元素，字典序越小
• 将所有字符串放入队列中排好序，然后重新从队列中获取

Java 版本代码如下：

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        if(strs == null || strs.length < 1) {
            return null;
        }
        // 重载比较函数
        PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            public int compare(String s1, String s2) {
                // 保证 s1 + s2 > s2 + s1 时，返回值大于0，否则返回值小于0
                // 保证queue中越靠近队头的元素，字典序越小
                return (s1 + s2).compareTo(s2 + s1);
            } 
        });
        // 放入队列中排好序
        for(String str : strs) {
            queue.offer(str);
        }
        StringBuilder res = new StringBuilder();
        // 重新从队列中获取
        while(queue.size() > 0) {
            res.append(queue.poll());
        }    
        return res.toString();
    }
}

复杂度分析：

时间复杂度 O(N)：将每个字符串放入队列，又从中获取，N为字符串数量
空间复杂度 O(1)：用到了队列和StringBuilder的额外空间

方法二：利用C++的stl

算法流程：

• 构建比较器，str1 + str2 < str2 + str1则返回true
• 使用stl的排序
• 排序后的数组连接起来即可，就是结果

c++ 版本代码如下：

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
     // 构建比较器
    static bool cmp(const string &a, const string &b) {
        return (a+b) < (b+a);
    }
    string minString(vector<string>& strs) {
        // 使用stl的排序
        sort(strs.begin(), strs.end(), cmp);
        // 排序后的数组连接起来即可
        string res;
        for (auto a : strs) {
            res += a;
        }
        return res;
    }
};

复杂度分析：

时间复杂度 O(NlogN)：进行了一轮排序的时间级别
空间复杂度 O(1)：不需要额外空间