从左或右穿越.左代码140:单词断点2

Question

我看过“羊教授的电子代码140:断词2”

YouTube视频

这里的CPP代码

下面是我自己的Python翻译代码。在这种情况下，我认为可以通过从右到左遍历代码来优化代码，因为代码只开始使用最后一个单词。我向leetcode提交了实现，从左向左提交了40 to，从右执行了36 to。

我相信左与右是不一样的。就像在函数式编程中，foldLeft通常(没有语言优化或特殊情况)比foldRight有优势。在这种情况下，我相信从右边接近比左边有优势。

请帮助我验证我的想法，或者令人信服地证明我错了。

从左开始(就像羊教授)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        dic = set(wordDict)
        memo = {}

        def internal(sc):
            if not sc:
                return []
            if sc in memo:
                return memo[sc]
            res = []
            if sc in dic:
                res.append(sc)

            for pos in range(1, len(sc)):
                right = sc[pos:]
                if right not in dic:
                    continue
                left = sc[:pos]
                lfls = internal(left)
                for lf in lfls:
                    res.append(lf + " " + right)
            memo[sc] = res
            return res
        return internal(s)

右转

    def wordBreak(self, s: str, wordDict):
        dic = set(wordDict)
        memo = {}

        def internal(sc):
            if not sc:
                return []
            if sc in memo:
                return memo[sc]
            res = []
            if sc in dic:
                res.append(sc)

            for pos in range(len(sc), -1, -1):
                right = sc[pos:]
                if right not in dic:
                    continue
                left = sc[:pos]
                lfls = internal(left)
                for lf in lfls:
                    res.append(lf + " " + right)
            memo[sc] = res
            return res
        return internal(s)
```

Answer 1

由于调度和正在运行的任何后台任务，4ms的运行时与正常的系统方差相比差异很小。我不相信这表明了右向左的性能优势。

这两种方法之间的唯一区别(据我所见)是您迭代字符串的顺序。从算法上讲，从右到左相当于倒转输入字符串，从左到右。没有理由这样做应该更快，因为这是完全相同的算法。

CPU中的分支预测和缓存命中可能会产生很小的差异，但这是因为输入稍有不同，CPU的操作方式也略有不同，但这将对基于输入的任意一种方法都有好处。然而，预期的相对性能是一样的。

对不起，我相信这里没有什么可改进的。