From Js to Dart code translation. Recursion and memoization-CodePudding

I'm following a video tutorial on YouTube ( Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges ) from a popular YouTube channel. In this video it teaches in Js and I'm trying to translate it into Dart, but even when my algorithm looks the same it doesn't work as expected.

This is what the function should do:

Write a function 'allConstruct(target, wordBank)' that accepts a target string and an array of strings. The function should return a 2D array containing all of the ways that the 'target' can be constructed by concatenating elements of the 'wordBank' array. Each element of the 2D array should represent one combination that constructs the 'target'. You may reuse elements of 'wordBank' as many times as needed.

-- Here is the Js code

const allConstruct = (target, wordBank) => {
  if (target === '') return [[]];

  const result = [];

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const suffix = target.slice(word.length);
      const suffixWays = allConstruct(suffix, wordBank);
      const targetWays = suffixWays.map(way => [ word, ...way ]);
      result.push(...targetWays);
    }
  }

  return result;
};

-- And here is my Dart translation

allContruct(String target, List<String> wordBank) {
  if (target == '') return [[]];

  final result = [];

  for (final word in wordBank) {
    print(word);
    if (target.startsWith(word)) {
      final suffix = target.split(word)[1];
      final suffixWays = allContruct(suffix, wordBank);
      final targetWays = suffixWays.map((way) => [word, ...way]);
      result.insert(0, targetWays);
    }
  }

  return result;
}

With the same input of the video https://www.youtube.com/watch?v=oBt53YbR9Kk&ab_channel=freeCodeCamp.org at 03:03:18 allContruct('purple',['purp', 'p', 'ur', 'le', 'purpl']) here is how it result:

JS : [['purp', 'le'],['p','ur','p','le']]

My Dart: [(), ([p, [ur]]), ([purp, [le]])]

Thank you in advance for any help!

CodePudding user response：

There are a few issues in your code.

First, type safety are important in Dart so I have added types where needed. This is mostly the return type of your method and your declaration of result variable where Dart cannot guess what type you want.

Second, the String.split method are not the same as String.slice from JavaScript. I have replaced that call with String.substring.

Third, result.push does not push to to the start of the list but instead to the end. But your result.insert(0, targetWays); are telling Dart to insert your elements from the 0 position of the list (the beginning).

I have replaced this with result.addAll since your targetWays are a lazy-evaluated Iterable.

With all this changes, I get the same output as you have written. Please tell me if something is not working as expected. And if so, please provide example of the situation where it does not work.

List<List<String>> allContruct(String target, List<String> wordBank) {
  if (target == '') return [[]];
  final result = <List<String>>[];

  for (final word in wordBank) {
    print(word);
    if (target.startsWith(word)) {
      final suffix = target.substring(word.length);
      final suffixWays = allContruct(suffix, wordBank);
      final targetWays = suffixWays.map((way) => [word, ...way]);
      result.addAll(targetWays);
    }
  }

  return result;
}

void main() {
  print(allContruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']));
  // [[purp, le], [p, ur, p, le]]
}