拼接字符串，得到字典序最小的结果

1、题目

给定一个由字符串组成的数组 strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。

2、思路

贪心策略：将数组中的字符串按字典序进行排序，然后按序拼接起来。

这种策略不对！！，因为存在反例：["b", "ba"]，字典序 b < ba，按照贪心策略得到的拼接字符串应该就是 bba，但是实际上 bab 这个拼接的结果是比 bba 小的。

//失败的贪心策略
if (str1 < str2) //str1的字典序 < str2的字典序
    str1在前;
else 
    str2在前;

真正有效的贪心策略：使用比较器判断两个字符串拼接后的字典序

//如果 str1 拼接上 str2 之后的字典序 < str2 拼接上 str1 之后的字典序
if (str1.str2 < str2.str1) 
    str1在前;
else
    str2在前;

为什么这种贪心策略是有效的？ 这就需要证明。

1. 首先需要证明该排序策略具有传递性，目的是为了证明在该种排序策略下得到的字符串是唯一的。

   传递性也就是要证明：根据 （1）a.b <= b.a；（2）b.c <= c.b，能否推导出 a.c <= c.a？

   例如字符串 “123” 和 “456”，拼接后为 “123456”，如果是 K 进制，那么这个拼接过程用数学符号代替就是 “123” $\times$ K³ + “456”。

   所有的字符串都可以看做数字，则一定是非负整数。

   进一步抽象化，假设所有字符串都是 K 进制的，那么 a.b = a $\times$ K^b长度 + b，再进一步替代，m(x) = K^x长度。

   那么第1）2)条件就可以进行改写：

   a.b <= b.a 可以改写为： a * m(b) + b <= b * m(a) + a ①

   b.c <= c.b 可以改写为：b * m(c) + c <= c * m(b) + b ②

   ①式左右两边同时减b，再同时乘c：a * m(b) *c <= c * b * m(a) + a * c - b * c

   ②式左右两边同时减b，再同时乘a：a * b * m(c) + a * c - b * a <= c * m(b) * a

   可得a * b * m(c) + a * c - b * a <= c * b * m(a) + a * c - b * c

   同时减(a * c )，得到 a * b * m(c) - b*a <= c * b * m(a) - b * c

   同时含因子 b，两边同时除以b：a * m(c) - a <= c * m(a) - c

   挪动a和c：a * m(c) +c <= c * m(a) + a 变成了a.c <= c.a，证明结束。

2. 证明得到的字符串一定是字典序最小的。

   先证明任意2个字符串如果交换顺序，字典序只会变大。然后任意3个，任意4个，任意5个，…

   现在需要证明 [… a $m_1$$m_2$ b …] <= [… b $m_1$$m_2$ a …]

   首先，如果仅仅是交换 a 和 $m_1$，那么根据传递性，a.$m_1$ <= $m1$.a，所以[… a $m_1$$m_2$ b …] <= […$m_1$ a $m_2$ b …]

   ​ 同理，又因为 a.$m_2$ <= $m_2$.a，所以 […$m_1$ a $m_2$ b …] <= […$m_1$$m_2$ a b …]

   ​ 同理，交换a和b，[…$m_1$$m_2$ a b …] <= […$m_1$$m_2$ b a …]

   ​ 再将b 和$m_2$ 交换，[…$m_1$$m_2$ b a …] <= […$m_1$ b $m_2$ a …]

   ​ 最后，交换b 和 $m_1$，所以得到 […$m_1$ b $m_2$ a …] <= […b $m_1$$m_2$ a …]

   ​ 总结来说就是： [… a $m_1$$m_2$ b …] <= [… b $m_1$$m_2$ a …]。

   所以交换a和b的顺序，字典序只会增大，不会变小。再去证明交换任意3个、4个、…等等，用数学归纳法推导出来。

但是，实际上贪心策略不需要证明也能知道其正确性。方法论：用暴力解+ 对数器 的方法验证贪心策略的正确性。

3、代码实现

C++ 版

/************************************************************************* > File Name: 034.拼接字符串字典序最小.cpp > Author: Maureen > Mail: [email protected] > Created Time: 四 6/30 21:19:41 2022 ************************************************************************/

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <ctime>
using namespace std;

vector<string> removeIndexString(vector<string> &strs, int index) {
    
    int n = strs.size();
    vector<string> ans(n - 1);

    int ansIndex = 0;
    for (int i = 0; i < n; i++) {
    
        if (i != index) {
    
            ans[ansIndex++] = strs[i];
        }
    }
    return ans;
}

set<string> process(vector<string> &strs) {
    
    set<string> ans;
    if (strs.size() == 0) {
    
        ans.insert("");
        return ans;
    }

    for (int i = 0; i < strs.size(); i++) {
    
        string first = strs[i];
        vector<string> nexts = removeIndexString(strs, i);
        set<string> next = process(nexts);
        for (string cur : next) {
    
            ans.insert(first + cur);
        }
    }
    return ans;
}

string lowestString1(vector<string> &strs) {
    
    if (strs.size() == 0) return "";
    set<string> ans = process(strs);
    auto it = ans.begin();
    return ans.size() == 0 ? "" : *it;
}



//方法二：
bool comp(const string &a, const string &b) {
    
    return a + b < b + a;
}

string lowestString2(vector<string> &strs) {
    
    if (strs.size() == 0) return "";
    sort(strs.begin(), strs.end(), comp);
    string res = "";
    for (int i = 0; i < strs.size(); i++) {
    
        res += strs[i];
    }

    return res;
}


//for test 
string generateRandomString(int len) {
    
    char *ans = new char[rand() % len + 1];
    for (int i = 0; i < strlen(ans); i++) {
    
        int value = rand() % 5;
        ans[i] = (rand() % 100 / (double)101) <= 0.5 ? (char)(65 + value) : (char)(97 + value);
    }
    return ans;
}


vector<string> generateRandomStringArray(int alen, int slen) {
    
    vector<string> ans(rand() % alen + 1);
    for (int i = 0; i < ans.size(); i++) {
    
        ans[i] = generateRandomString(slen);
    }
    return ans;
}


vector<string> copyStringArray(vector<string> &arr) {
    
    vector<string> ans(arr.size());
    for (int i = 0; i < ans.size(); i++) {
    
        ans[i] = arr[i];
    }

    return ans;
}


int main() {
    
    srand(time(0));
        
    int arrLen = 6;
    int strLen = 5;

    int testTime = 10001;

    cout << "test begin" << endl;

    for (int i = 0; i < testTime; i++) {
    
        vector<string> arr1 = generateRandomStringArray(arrLen, strLen);
        vector<string> arr2 = copyStringArray(arr1);

        if (lowestString1(arr1) != lowestString2(arr2)) {
    
            for (string str : arr1) {
    
                cout << str << " , ";
            }
            cout << endl;
            cout << "Oops!" << endl;
            break;
        }
        if (i && i % 100 == 0) cout << i << " cases passed!" << endl;
    }

    cout << "finish!" << endl;

    return 0;
}

Java 版

package class13;

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

public class Code05_LowestLexicography {
    
	
	//方法一：暴力解
	public static String lowestString1(String[] strs) {
    
		if (strs == null || strs.length == 0) {
    
			return "";
		}
		TreeSet<String> ans = process(strs);
		return ans.size() == 0 ? "" : ans.first();
	}

	// strs中所有字符串全排列，返回所有可能的结果
	public static TreeSet<String> process(String[] strs) {
    
		TreeSet<String> ans = new TreeSet<>();
		if (strs.length == 0) {
    
			ans.add("");
			return ans;
		}
		for (int i = 0; i < strs.length; i++) {
    
			String first = strs[i];
			String[] nexts = removeIndexString(strs, i);
			TreeSet<String> next = process(nexts);
			for (String cur : next) {
    
				ans.add(first + cur);
			}
		}
		return ans;
	}

	// {"abc", "cks", "bct"}
	// 0 1 2
	// removeIndexString(arr , 1) -> {"abc", "bct"}
	public static String[] removeIndexString(String[] arr, int index) {
    
		int N = arr.length;
		String[] ans = new String[N - 1];
		int ansIndex = 0;
		for (int i = 0; i < N; i++) {
    
			if (i != index) {
    
				ans[ansIndex++] = arr[i];
			}
		}
		return ans;
	}

	//方法二：使用对数器
	public static class MyComparator implements Comparator<String> {
    
		@Override
		public int compare(String a, String b) {
    
			return (a + b).compareTo(b + a);
		}
	}

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

	// for test
	public static String generateRandomString(int strLen) {
    
		char[] ans = new char[(int) (Math.random() * strLen) + 1];
		for (int i = 0; i < ans.length; i++) {
    
			int value = (int) (Math.random() * 5);
			ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
		}
		return String.valueOf(ans);
	}

	// for test
	public static String[] generateRandomStringArray(int arrLen, int strLen) {
    
		String[] ans = new String[(int) (Math.random() * arrLen) + 1];
		for (int i = 0; i < ans.length; i++) {
    
			ans[i] = generateRandomString(strLen);
		}
		return ans;
	}

	// for test
	public static String[] copyStringArray(String[] arr) {
    
		String[] ans = new String[arr.length];
		for (int i = 0; i < ans.length; i++) {
    
			ans[i] = String.valueOf(arr[i]);
		}
		return ans;
	}

	public static void main(String[] args) {
    
		int arrLen = 6;
		int strLen = 5;
		int testTimes = 10000;
		System.out.println("test begin");
		for (int i = 0; i < testTimes; i++) {
    
			String[] arr1 = generateRandomStringArray(arrLen, strLen);
			String[] arr2 = copyStringArray(arr1);
			if (!lowestString1(arr1).equals(lowestString2(arr2))) {
    
				for (String str : arr1) {
    
					System.out.print(str + ",");
				}
				System.out.println();
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}