题目描述

给定字符串，对其进行逆序排序。

字符逆序是指从z到a排序，比如对两个字符串排序时，先比较第一个字符，按照字符逆序将z排在a的前面，当第一个字符相等时按照第二个字符进行排序，以此类推。

特殊情况：

  1. 空字符串需要排在最前面；
  2. 若一个短字符串是另一个长字符串的前缀则短字符串排在前面

请自行实现代码进行排序，不可直接调用sort等排序方法。

样例

输入

waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei,menpiao,jiudian

输出

waimai,menpiao,meishi,lvyou,lvyoujingdian,liren,jiudian,jiehun,jiaopei,dache

# -*- coding: utf-8 -*-
# @Time         : 2019-10-16 16:15
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : meituan.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


from collections import defaultdict


"""
对字符串进行字典序倒序排序，唯一要注意的是当s1是s2的前缀的时候，s1要在s2之前。

**这里是最大的坑，因为我们本来在字符串排序的时候如果s2 = s1 + s3的话，
那么s1 < s2，在倒序的时候就是s2, s1。这里题目特意变成了s1, s2的顺序，也因此使用快排等算法是不能
直接AC的**

解题思路：
其实我们搞清楚前面那个坑之后就可以继续用快排进行排序，只需要将比较函数修改一下即可
"""


def bucket_based_recursive():
    """
    这里我是按照题目的要求进行递归排序的。
    首先比较所有字符的首字符，然后按照首字符将所有单词划分到对应的桶，
    只要桶内的元素大于1就重复上述步骤(通过递归实现)，否则加入到结果列表中
    """
    def sort(data, idx):
        nonlocal ans
        bucket = defaultdict(list)
        data.sort()  # 这里排序是为了处理s1是s2的前缀的情况
        last_key = None
        prefix = False
        # 循环内对列表的末尾元素进行操作，可以减少时间复杂度
        while data:
            # 这里的分支是为了处理空字符串
            if not data[-1]:
                ans.append(data.pop())
            try:
                last_key = data[-1][idx]
                bucket[data[-1][idx]].append(data.pop())
            except IndexError:
                prefix = True  # 标记是否有前缀出现
                # 如果是前缀的话就需要将前缀加入到后面，这样在倒序之后才能符合题目要求
                bucket[last_key].append(data.pop())
        # 对各个桶进行排序
        bucket = sorted(bucket.items(), key=lambda x: x[0])
        # 若桶内元素小于2或者出现了前缀则将最后一个桶的元素加入结果列表中
        for idx, item in enumerate(bucket):
            if prefix and idx == len(bucket) - 1 or len(item[1]) < 2:
                ans += item[1]
            else:  # 否则对该桶递归进入下一次排序，注意将下一次需要比较的下标+1
                sort(item[1], idx + 1)

    words = "waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei," \
            "menpiao,jiudian".split(',')
    # ans = "waimai,menpiao,meishi,lvyou,lvyoujingdian,liren,jiudian,
    #       jiehun,jiaopei,dache"

    ans = []
    sort(words, 0)
    print(','.join(ans[::-1]))


def quick_sort_based():
    def cmp_to_key(mycmp):
        # Convert a cmp= function into a key= function
        class K:
            def __init__(self, obj, *args):
                self.obj = obj

            def __lt__(self, other):
                return mycmp(self.obj, other.obj) < 0

            def __gt__(self, other):
                return mycmp(self.obj, other.obj) > 0

            def __eq__(self, other):
                return mycmp(self.obj, other.obj) == 0

            def __le__(self, other):
                return mycmp(self.obj, other.obj) <= 0

            def __ge__(self, other):
                return mycmp(self.obj, other.obj) >= 0

            def __ne__(self, other):
                return mycmp(self.obj, other.obj) != 0
        return K

    string = "waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei," \
             "menpiao,jiudian"
    strs = string.split(",")

    def cmp(s1, s2):
        """
        如果s1是空字符串，那么s1 > s2
        如果s1是非空字符串，而s2是空字符串，那么s1 < s2
        如果s1对应下标的字符 > s2对应下标的字符，那么s1 > s2
        如果s1对应下标的字符 < s2对应下标的字符，那么s1 < s2

        如果在合法下标的比较中s1和s2对应下标的字符都相等，那么较短的字符串较大，也就是前缀更大
        例如 "abc" > "abcd"
        :param s1: 待比较的字符串1
        :param s2: 待比较的字符串2
        :return: 若s1 > s2，返回1，若s1 < s2，返回-1，不存在相等返回0的情况
        """

        if not s1:
            return 1
        if not s2:
            return -1
        for x in range(min(len(s1), len(s2))):
            if s1[x] > s2[x]:
                return 1
            elif s1[x] < s2[x]:
                return -1
        return 1 if len(s1) < len(s2) else -1

    strs.sort(key=cmp_to_key(cmp), reverse=True)
    print(",".join(strs))


def main():
    bucket_based_recursive()
    quick_sort_based()


if __name__ == '__main__':
    main()