题目:给定一个字符串的数组strs,请找到一种拼接顺序,使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的,并返回这个字符串。
例子1:输入{ba”,“b”},输出”bab“
例子2:输入{“abc”,“de”},输出“abcde”
在这道题中,贪心策略就是排序策略。
1.什么是字典序呢?
①假设字符串长度相等。“abc”和“bce”比较?
将它们看成数和数的比较即可。从最高位开始比,a的ASCII码值小于b的ASCII码。所以abc小于“bce”。
②假设字符串长度不相等。“b和ba比较?
首先在字符串长度小的“b”后面补上ASCII码值最小的数(这里为了方便就写成0)。变成b0和ba得比较。
先看最高位都是b。然后看第二位“0”a。所以“b”小于“ba”。
2.排序策略一(错误)
字符串各自按照字典序排,排完之后拼接起来。如果str1str2,那么str1放到str2的前面;反之str2放到str1的前面。
反例:{“ba”,b}。
因为bba,b放到“ba的前面。字典序最小就是bba。
正确结果应该是bab。
3.排序策略二(正确)
如果前一个字符串拼接后一个字符小于后一个字符串拼接上前一个字符串。前一个字符串放前面。如果str1.str2str2.str1,那么str1放到str2的前面。否则str2放前面。
例子:{“ab”,c}。
比较”abc“和“cba”的大小。因为“abc”小于“cba。所以ab放到“c”的前面。
4.实现代码
4.为什么策略一错误而策略二正确呢?
假设现在有甲乙丙三个元素。在比较器里规定:
甲和乙相遇:甲在前面。
乙和丙相遇:乙在前面。
甲和丙相遇:丙在前面。
上述策略的结果形成了一个环。无法正确比较出他们的大小。不具备传递性。因此策略是否正确第一点就是策略是否具备传递性。
①策略二的传递性证明:
证明:如果将a.b理解为一个k进制的数。a.b=a*k^(b长度)+b。
假设,25连接成25=*10^2+25。这里的k为10.将k^(b长度)记为m().
证明过程②怎么证明所产生的序列就是字典序最小的。
假设有这样的序列“.....a....m1...m2....b...
a和b交换之后所产生的序列一定比原序列大。
上述证明是不是很繁琐呢?
结论:不要纠结于贪心策略正确性的证明。