Traversing from left or from right - Leetcode 140: Word Break II I have watched Professor Sheep's Leetcode 140: Word Break II

YouTube video here

CPP code here

My own Python translation code is below. I am thinking that the code can be optimized by traversing from right to left in this case as the code only start working with the last word. I have submitted both implementation to leetcode and traversing from left executed with 40ms and traversing from right executed with 36ms. 

I believe that left and right are not the same. Just like in functional programming where foldLeft generally (no language optimization or special cases) have advantage over foldRight. In this case, I believe that approaching from Right has advantage over Left.

Please help me validate my thinking or prove me wrong convincingly.

From Left (like Professor Sheep)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -&gt; 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)


From Right

    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)
```
The difference in runtime of 4ms is very small compared to normal system variance due to scheduling and whatever background tasks are running. I don't believe that indicates a performance benefit right vs left.

And the only difference between the two approaches (as far as I can see) is which order you iterate the string. Algorithmically speaking going right to left is equivalent to reversing the input strings and going left to right. There is no reason why that should be any faster as it's the exact same algorithm.

There maybe be a small difference due to branch prediction and cache hits in the CPU but this is because the input is slightly different and it exercises the CPU every do slightly differently but it will benefit either method randomly based on the input. The expected relative performance, however, is the same.

I'm sorry but I believe the is nothing to improve here.