4 ms·

Having looked at the code a bit I stumbled onto this: https://github.com/alexmacarthur/striff/blob/master/src/utils/getAllParts.ts https://github.com/alexmacar

Having looked at the code a bit I stumbled onto this: https://github.com/alexmacarthur/striff/blob/master/src/utils/getAllParts.ts https://github.com/alexmacarthur/striff/blob/master/src/util... This... can't be right. Can you explain how your algorithm differs from, in particular, this one: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution https://en.wikipedia.org/wiki/Longest_common_subsequence_pro... Also, why does it differ from that?

melony 4y ago
I would recommend using an optimized permutations library/generator on the string start and end indices instead of directly manipulating the slices.
- samatman 4y ago
  > permutations ! Hey, you said it. I would recommend against permutations
  - melony 4y ago
    You still need to generate all the permutations, even if you use dynamic programming.
romellem 4y ago
Aside from the fact that they are basically generating power sets, if you don’t need all the values at once, a better method would be to use a generator function if all you are doing is iterating. That way you don’t need to create all the values in memory first. A library that I like for this is https://www.npmjs.com/package/generatorics https://www.npmjs.com/package/generatorics although there may be more modern ones available.
- samatman 4y ago
  > Aside from the fact that they are basically generating power sets ! String diff calls for an M x N cost matrix and simple dynamic programming with tail calls (or you can unwind it into loops if you have to). Not... not power sets.