Concatenate strings to get the result with the smallest dictionary order

1、 subject

Given an array of strings strs, You have to put all the strings together , Return to all possible splicing results , The result of minimum dictionary order .

2、 Ideas

Greedy strategy ： Sort the strings in the array in dictionary order , Then splice them in order .

This strategy incorrect ！！, Because there are counterexamples ：["b", "ba"], Dictionary order b < ba, The splicing string obtained according to the greedy strategy should be bba, But actually bab The result of this splicing is better than bba Small .

// Failed greedy strategy 
if (str1 < str2) //str1 Dictionary sequence  < str2 Dictionary sequence 
    str1 before ;
else 
    str2 before ;

A really effective greedy strategy ： Use the comparator to judge the dictionary order after the splicing of two strings

// If  str1  Splicing  str2  The following dictionary sequence  < str2  Splicing  str1  The following dictionary sequence 
if (str1.str2 < str2.str1) 
    str1 before ;
else
    str2 before ;

Why is this greedy strategy effective ？ This requires proof .

1. First, we need to prove that the sorting strategy has Transitivity , The purpose is to prove that the string obtained under this sort of sorting strategy is unique .

   Transitivity is to prove ： according to （1）a.b <= b.a;（2）b.c <= c.b, Can we deduce a.c <= c.a？

   Like strings “123” and “456”, After splicing, it is “123456”, If it is K Base number , Then this splicing process is replaced by mathematical symbols “123” $\times$ K³ + “456”.

   All strings can be regarded as numbers , Then it must be a nonnegative integer .

   Further Abstract , Assume that all strings are K It's binary , that a.b = a $\times$ K^{b length} + b, Further substitution ,m(x) = K^{x length} .

   So the first 1）2) Conditions can be rewritten ：

   a.b <= b.a I could rewrite it as ： a * m(b) + b <= b * m(a) + a ①

   b.c <= c.b I could rewrite it as ：b * m(c) + c <= c * m(b) + b ②

   ① The left and right sides of the formula are reduced at the same time b, Multiply at the same time c：a * m(b) *c <= c * b * m(a) + a * c - b * c

   ② The left and right sides of the formula are reduced at the same time b, Multiply at the same time a：a * b * m(c) + a * c - b * a <= c * m(b) * a

   Available a * b * m(c) + a * c - b * a <= c * b * m(a) + a * c - b * c

   Simultaneous subtraction (a * c ), obtain a * b * m(c) - b*a <= c * b * m(a) - b * c

   It also contains factors b, Divide both sides at the same time b：a * m(c) - a <= c * m(a) - c

   Move a and c：a * m(c) +c <= c * m(a) + a Turned into a.c <= c.a, End of proof .

2. Prove that the resulting string must be the least lexicographically ordered .

   First prove any 2 String if the exchange order , The dictionary order will only get bigger . And then whatever 3 individual , arbitrarily 4 individual , arbitrarily 5 individual ,…

   Now we need to prove [… a $m_1$$m_2$ b …] <= [… b $m_1$$m_2$ a …]

   First , If it's just exchange a and $m_1$, Then according to Transitivity ,a.$m_1$ <= $m1$.a, therefore [… a $m_1$$m_2$ b …] <= […$m_1$ a $m_2$ b …]

   ​ Empathy , Again because a.$m_2$ <= $m_2$.a, therefore […$m_1$ a $m_2$ b …] <= […$m_1$$m_2$ a b …]

   ​ Empathy , In exchange for a and b,[…$m_1$$m_2$ a b …] <= […$m_1$$m_2$ b a …]

   ​ then b and $m_2$ In exchange for ,[…$m_1$$m_2$ b a …] <= […$m_1$ b $m_2$ a …]

   ​ Last , In exchange for b and $m_1$, So get […$m_1$ b $m_2$ a …] <= […b $m_1$$m_2$ a …]

   ​ In conclusion, it is ： [… a $m_1$$m_2$ b …] <= [… b $m_1$$m_2$ a …].

   So exchange a and b The order of , The dictionary order will only increase , It doesn't get smaller . Then prove that the exchange is arbitrary 3 individual 、4 individual 、… wait , It is deduced by mathematical induction .

however , In fact, the greedy strategy can know its correctness without proof . methodology ： use Violent solution + Logarithmic apparatus To verify the correctness of the greedy strategy .

3、 Code implementation

C++ edition

/************************************************************************* > File Name: 034. The concatenated string dictionary order is the smallest .cpp > Author: Maureen > Mail: [email protected] > Created Time:  Four  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;
}



// Method 2 ：
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 edition

package class13;

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

public class Code05_LowestLexicography {
    
	
	// Method 1 ： Violent solution 
	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 All strings in the are arranged completely , Returns all possible results 
	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;
	}

	// Method 2 ： Use logarithm 
	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!");
	}
}