CODEWITHSUNDEEP
javascriptc#algorithm
Edon
Edon

Reputation: 1216

display all Letter Tile Possibilities

I was doing the leetcode problem Letter Tile Possibilities. Which is where you print out every possible sequence of a given string.

I have a working solution below. However, as a followup, I wanted to try and display all the sequences, but am having issues. Given string "AAB", it prints the correct number of sequences, but repeats several of the sequences, seen here:

enter image description here

note: B is a repeated sequence, and the sequence ABA never appears.

var numTilePossibilities = function (tiles) {
    let map = getTileMap(tiles);
    return helper(map, "");
};

function helper(map, currString) {
    let sum = 0;
    for (let character in map) {
        if (map[character] !== 0) {
            sum++;
            currString += character;
            map[character] = map[character] - 1;
            sum += helper(map, currString);
            map[character] = map[character] + 1;
            console.log('completed string: ', currString);
            currString = '';
        }
    }
    return sum;
}

I have found other solutions that I have edited to print out out all the sequences, and it prints correct, for example this c# solution: enter image description here enter image description here

But can't determine the difference between the solutions that is causing the sequences to print correctly.

How can I print out every string sequence for this problem?

Upvotes: 0

Views: 449

Answers (1)

M Oehm
M Oehm

Reputation: 29126

Your problem is in the way that you modify currString after printing it. If you want to undo the appending of character, you should remove that character instead of setting the string to an empty string:

currString = currString.substring(0, currString.length - 1);

Perhaps it is better to leave currString as it is and create a new string only for the inner scope:

function helper(map, currString) {
    let sum = 0;
    for (let character in map) {
        if (map[character] !== 0) {
            let newString = currString + character;            
            sum++;

            map[character] = map[character] - 1;
            sum += helper(map, newString);
            map[character] = map[character] + 1;

            console.log('completed string: ', newString);
        }
    }

    return sum;
}

Upvotes: 1

Related Questions