为何不同字符会影响getPositions方法的输出顺序？

代码实现 #

class Solution(object):
    def getPositions(self, s):
        mapping = {}
        for i in range(len(s)):
            if s[i] not in mapping:
                mapping[s[i]] = [i]
            elif s[i] in mapping:
                mapping[s[i]].append(i)
        return mapping.values()

问题描述 #

预期执行getPositions("paper") == getPositions("title")返回True，但实际输出显示两个结果的列表顺序不一致：

[[1], [0, 2], [4], [3]]   ==   [[1], [4], [0, 2], [3]] 

原因分析 #

核心问题出在字典的键顺序上：

• 即使在Python 3.7及以后（dict开始保留键的插入顺序），两个字符串的字符插入顺序对应的键序列仍不相同：
  • 处理"paper"时，字符首次出现的顺序是p→a→e→r，字典的键顺序为p, a, e, r，对应values()返回的列表顺序由这个键顺序决定
  • 处理"title"时，字符首次出现的顺序是t→i→l→e，字典的键顺序为t, i, l, e，对应values()返回的列表顺序也由这个键顺序决定
• 由于两个字典的键顺序完全不同，values()返回的列表自然顺序不一致，直接用==比较时结果为False。

解决方案 #

要让两个结果的比较符合预期，需要对返回的values进行标准化排序，比如按每个子列表的第一个元素（即字符首次出现的位置）排序后再比较：

def getPositions(s):
    mapping = {}
    for i in range(len(s)):
        if s[i] not in mapping:
            mapping[s[i]] = [i]
        else:
            mapping[s[i]].append(i)
    # 按子列表的第一个元素排序，统一输出顺序
    return sorted(mapping.values(), key=lambda x: x[0])

此时getPositions("paper") == getPositions("title")会返回True。

内容的提问来源于stack exchange，提问作者Chika