【leetcode】1163. Last Substring in Lexicographical Order

题目如下：

Given a string s, return the last substring of s in lexicographical order.

Example 1:
Input: "abab"

Output: "bab"

Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".
Example 2:
Input: "leetcode"

Output: "tcode"
Note:

1 <= s.length <= 10^5

s contains only lowercase English letters.

解题思路：我的方法是找出s中的最大字符max_char，然后以max_char为分隔符分割s。例如s="azazazzzazbzc"，分割后得到item_list : ['za', 'za', 'zzza', 'zb', 'zc'] ，注意这里舍弃了从字符串头部到第一个max_char之间的部分，同时如果有连续多个max_char出现，合并为同一个子串。接下来遍历item_list,找出最大的子串即可，这里有两点要注意，如果item_list中两个元素相等，那么继续比较这两个元素后面的元素，直到找出不一致为止；另外如果一个item是另一个item的前缀字符串，那么较短的item的值为大。

代码如下：

class Solution(object):

    def lastSubstring(self, s):

        """

        :type s: str

        :rtype: str

        """

        max_char = 'a'

        for i in s:

            max_char = max(max_char,i)

        item_list = []

        sub = ''

        for i in s:

            if sub == '' and i != max_char:

                continue

            elif sub == '' and i == max_char:

                sub += i

            elif sub != '' and i != max_char:

                sub += i

            elif sub != '' and i == max_char and sub[-1] == max_char:

                sub += i

            elif sub != '' and i == max_char and sub[-1] != max_char:

                item_list.append(sub)

                sub = i

            elif sub != '' and i != max_char:

                sub += i

        if len(sub) > 0:item_list.append(sub)

        print item_list

        inx = 0

        sub = item_list[0]

        for i in range(1,len(item_list)):

            if item_list[i] == sub:

                tmp_inx = i + 1

                inx_copy = inx + 1

                while inx_copy < len(item_list) and tmp_inx < len(item_list):

                    if item_list[inx_copy] < item_list[tmp_inx]:

                        sub = item_list[i]

                        inx = i

                        break

                    inx_copy += 1

                    tmp_inx += 1

            elif len(item_list[i]) < len(sub) and item_list[i] == sub[:len(item_list[i])] and i < len(item_list) - 1:

                sub = item_list[i]

                inx = i

            elif sub < item_list[i] and not (len(sub) < len(item_list[i]) and sub == item_list[i][:len(sub)]):

                sub = item_list[i]

                inx = i

        res = ''

        for i in range(inx,len(item_list)):

            res += item_list[i]

        return res

巴特西

【leetcode】1163. Last Substring in Lexicographical Order

最新文章

热门文章