Traversing from left or from right - Leetcode 140: Word Break II

Question

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]) -> 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)
```

• cole: It is not always the case that left folds have advantage over right folds, at least in lazy languages like Haskell (stackoverflow.com/q/384797/5309823) - fold direction is a generally confusing subject though (for me), so perhaps there are not similar issues in other functional languages.
• wispymisty: This algorithm has no relation to foldl or foldr apart from the movement direction. In functional programming, fold left is left associative and fold right is right associative. Fold left is lazy and fold right is not. As for this algorithm, you may be able to find data set that favors one direction or other but, theoretically, the direction part are one and the same whether you go from left to right or right to left.
• Win Myo Htet: I agree that fold left and fold right has nothing to do with this algorithm. I just want to bring out the analogy about some code not treating left and right the same. I also agree that there might be some data that favours one direction over the other. However the majority of the data for the language related ones (cat, dog, words... etc) used in this code are left to right. Thus, I think that processing from the right here will have a bit of advantage.

Answer 1

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.