Raku: 解 work-break-ii

word-break-ii 是一則在 leetcode 上的題目。在前文 Perl6: 解 work-break-ii 中提到了，「事後重新想過一輪，覺得應該也可以由前方開始向後搜。或許日後再撰文筆記。」，此文為其之後記：

程式碼如後。基本上是先用 Str#starts-with 這個方法找出在 $s 字串中每個位置 $i 能有哪些選擇，並存入 @choices[$i] 中。

在這版本裡，初次建完 @choices 之後，又多花了一個迴圈從 @choices 最後走到前，判斷出無法使用的選項，然後移除。這裡所謂「無法使用」，指的是「下一步就沒有選項」的意思。

#!/usr/bin/env raku
# work-break-ii.raku
sub word-break-ii (Str $s, @wordDict) returns Array {
    my @choices = (1..$s.chars).map({ Array.new });
    loop (my $i = 0; $i < $s.chars; $i++) {
        my $sx = $s.substr($i);
        for @wordDict.grep({ $sx.starts-with($_) }) -> $w {
            @choices[$i].push($w);
        }
    }

    for (0...@choices.end).reverse -> $i {
        @choices[$i] = @choices[$i].grep(-> $w {
            my $j = $i + $w.chars;
            $j == @choices.end || @choices[$j].elems > 0
        });
    }

    my @stash;
    for @choices.head.values -> $w {
        @stash.push( $w.chars => [$w] );
    }

    my @ans;
    while @stash.elems > 0 {
        my $it = @stash.shift();
        my $i = $it.key;
        my @ansx = $it.value;

        if ($i == $s.chars) {
            @ans.push( @ansx.join(" ")  )
        } else {
            for @choices[$i].values -> $w {
                @stash.push( ($i + $w.chars)  => [$w].append(@ansx) );
            }
        }
    }

    return @ans;
}

say word-break-ii( "cat", ["cat", "cats", "and", "sand", "dog"]).perl;
say word-break-ii( "catsanddog", ["cat", "cats", "and", "sand", "dog"]).perl;
say word-break-ii( "pineapplepenapple", ["pen", "pine", "pineapple", "apple", "pie"] ).perl;
say word-break-ii( "catsandog", ["cats", "dog", "sand", "and", "cat"]).perl;