考虑从后向前处理。也就是我们先判断从一个非终止字符开始能否变换为终止状态。可以用类似拓扑排序的方法来解决，过程中我们可以同时记录每个非终止字符变换的终止状态的长度奇偶性。有一些非终止字符可以同时变换到奇偶两种长度，我们也标记这样的字符。最后，如果起始字符可以终止，且其长度为奇数，或能到达一个任意奇偶性的字符，则有解。

时间复杂度 $O(n+m+\sum k_i)$。