HackerRank Grid Challenge代码无法通过边缘用例求助

问题描述 #

给定由ASCII[a-z]字符组成的正方形网格，需完成两个步骤：

• 将每行元素按字母升序重排
• 判断各列是否从上到下按字母升序排列，满足则返回YES，否则返回NO

原代码 #

def gridChallenge(grid):
    last_string = ""
    
    for string in grid:
        string = ''.join(sorted(string))
        print(string)
        if string < last_string:
            return "NO"
        last_string = string

    return "YES"

错误原因 #

原代码通过比较排序后行的字典序来判断列是否有序，这个逻辑不成立。字典序仅要求从左到右第一个不同字符满足递增，而列有序需要每一列的所有字符都从上到下递增，二者并不等价。

未通过的边缘用例 #

比如这个2x3网格：

grid = ["zab", "cac"]

排序后每行变为：

• 第一行："abz"
• 第二行："acc"

原代码会因"abz" < "acc"判定符合条件，最终返回YES，但实际第三列字符z（第一行）大于c（第二行），不满足列升序要求，正确结果应为NO。

修复后的代码 #

def gridChallenge(grid):
    # 对所有行进行排序
    sorted_rows = [''.join(sorted(row)) for row in grid]
    # 逐列检查是否升序
    col_count = len(sorted_rows[0])
    row_count = len(sorted_rows)
    
    for col in range(col_count):
        for row in range(1, row_count):
            if sorted_rows[row][col] < sorted_rows[row-1][col]:
                return "NO"
    return "YES"

修复说明 #

1. 先完成所有行的排序，得到排序后的网格
2. 遍历每一列，从第二行开始逐一比较当前行与上一行的同列字符
3. 若某一列出现字符递减，立即返回NO；所有列均满足升序则返回YES

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