拼接所有的字符串产生字典序最小的字符串

拼接所有的字符串产生字典序最小的字符串_牛客题霸_牛客网

问题简述

给定一个长度为 n 的字符串数组 strs ，请找到一种拼接顺序，使得数组中所有的字符串拼接起来组成的字符串是所有拼接方案中字典序最小的，并返回这个拼接后的字符串。

思路：自定义排序

• Python 中基于比较的自定义排序写法：

  from functools import cmp_to_key
  
  def cmp(a, b):
      """"""
      # 若返回值 >0 则交换 a, b 顺序，反之保持
  
  l = sorted(l, key=cmp_to_key(cmp))

• 本题中可以按如下定义 cmp 函数，表示如果 a + b 比 b + a 的字典序大的话，就应该交换两个的位置；

  def cmp(a, b):
      return 1 if a + b > b + a else -1

Python

class Solution:
    def minString(self , strs: List[str]) -> str:
        from functools import cmp_to_key
        
        key = cmp_to_key(lambda a, b: 1 if a + b > b + a else -1)
        ss = sorted(strs, key=key)
        return ''.join(ss)