算法--拼接最小字典序

转载请标明出处http://www.cnblogs.com/haozhengfei/p/63b2460bceae42e55f0c2d150bde663b.html

拼接最小字典序

拼接最小字典序练习

第8节拼接最小字典序练习题

对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。

给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。

测试样例：

["abc","de"],2

"abcde"

代码自动补全

 
 
 
 
 
import java.util.*;
public class Prior {
    public String findSmallest(String[] strs, int n) {
        // 这里使用插入排序
        for (int i = 1; i < strs.length; i++) {
            // 当前需要排序的元素
            String target = strs[i];
            // j标记当前位置
            int j = i;
            while(j>0 && (target+strs[j-1]).compareTo(strs[j-1]+target) < 0){
                strs[j] = strs[j-1];
                j--;
            }
            strs[j] = target;
        }
        StringBuffer sb = new StringBuffer();
        for(String str: strs){
            sb.append(str);
        }
        return sb.toString();
    }
    //方法二，使用Arrays.sort()方法
    public String findSmallest2(String[] strs, int n) {
        if(strs == null){
            return null;
        }
        Comparator<String> c = new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                String str1first = str1 + str2;
                String str2first = str2 + str1;
                return str1first.compareTo(str2first);
            }
        };
        Arrays.sort(strs, c);
        StringBuffer str = new StringBuffer();
        for(int i = 0; i < n; i++){
            str.append(strs[i]);
        }
        return str.toString();
    }
}
 
 

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例

算法--拼接最小字典序

拼接最小字典序

第8节 拼接最小字典序练习题

第8节拼接最小字典序练习题