如何判断单词数组是否按自定义顺序排序？求更优解法

嘿，我来帮你搞定这个问题！咱们的目标是验证words数组是否严格遵循ordering定义的自定义字典序排列对吧？先理清楚核心逻辑，再给出通用高效的Perl实现。

核心思路 #

要高效验证排序是否符合要求，关键是把自定义顺序转换成可快速查询的映射，然后逐对检查相邻单词：

1. 构建优先级哈希表：把ordering里的每个字符映射到它的索引位置——索引越小，优先级越高（越应该排在前面）。
2. 逐对比较相邻单词：对每一对相邻单词，逐字符对比：
   • 找到第一个不同的字符，看它们的优先级是否符合顺序；
   • 如果一个单词是另一个的前缀，那么短单词必须排在前面才算符合要求；
   • 只要有一对不符合，直接返回false，全部符合则返回true。

通用Perl实现 #

这个版本能处理任意长度的单词，还兼容words中出现ordering外字符的情况（默认这类字符优先级最低）：

# 辅助函数：判断前一个单词是否应该排在后一个单词前面
sub is_valid_pair {
    my ($prev_word, $next_word, $order_map) = @_;
    my @prev_chars = split //, $prev_word;
    my @next_chars = split //, $next_word;
    my $min_length = @prev_chars < @next_chars ? @prev_chars : @next_chars;

    # 逐字符对比
    for my $i (0 .. $min_length - 1) {
        # 不在ordering里的字符默认优先级设为ordering的长度（最低）
        my $prev_rank = $order_map->{$prev_chars[$i]} // scalar(keys %$order_map);
        my $next_rank = $order_map->{$next_chars[$i]} // scalar(keys %$order_map);

        if ($prev_rank < $next_rank) {
            return 1; # 前单词优先级更高，符合顺序
        } elsif ($prev_rank > $next_rank) {
            return 0; # 前单词优先级更低，不符合
        }
        # 字符相等则继续下一个
    }

    # 前面字符都相同，短单词必须在前
    return @prev_chars <= @next_chars;
}

# 主函数：验证整个words数组的顺序
sub check_custom_order {
    my ($words_ref, $ordering_ref) = @_;
    # 空数组或单个元素直接返回true
    return 1 if @$words_ref <= 1;

    # 构建字符->优先级的哈希表
    my %order_map;
    @order_map{@$ordering_ref} = 0 .. $#$ordering_ref;

    # 遍历所有相邻单词对
    for my $i (0 .. $#$words_ref - 1) {
        unless (is_valid_pair($words_ref->[$i], $words_ref->[$i+1], \%order_map)) {
            return 0;
        }
    }
    return 1;
}

# 测试示例1
my @words1 = ('cc', 'cb','bb','ac');
my @ordering1 = ('c','b','a');
print check_custom_order(\@words1, \@ordering1) ? "true\n" : "false\n"; # 输出true

# 测试示例2
my @words2 = ('cc', 'cb','bb','ac');
my @ordering2 = ('b','c','a');
print check_custom_order(\@words2, \@ordering2) ? "true\n" : "false\n"; # 输出false

方案优势 #

• 通用性强：不管单词长短、是否包含ordering外的字符，都能正确处理；
• 高效简洁：哈希表查询是O(1)，整体时间复杂度为O(N*M)（N是单词数量，M是单词平均长度），已是这类问题的最优复杂度；
• 可读性高：拆分了辅助函数，逻辑清晰，后续维护或扩展都很方便。

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