Stickers To Spell Word


  • 0

    Click here to see the full article post


  • 0
    D

    Thank you for sharing.
    Did I miss something? I think t isn't the enough length in "stickersCount = new int[stickers.length][t];" for stickers letter count. Since "int j = index[c - 'a'];" j may bigger than t. Are something missed? May you help me figure it out?
    stickersCount = new int[stickers.length][t];
    for (int i = 0; i < stickers.length; i++) {
    for (char c: stickers[i].toCharArray()) {
    int j = index[c - 'a'];
    if (j >= 0) stickersCount[i][j]++;
    }
    }


  • 0
    L

    Excellent Solution Article, dude, you are really good at explaining complicated things to newbies like me. I checked the top contestants solutions and did not understand even a piece of their dynamic programming code. But after reading your article, I can work out my own dynamic programming code. Thanks a billion. Hope you could produce more great tutorials like this one.


  • 1

    @donggua_fu t is the number of unique characters in target. The sticker counts have been re-indexed so that they only count these characters. For example if target is 'bdf' then a sticker like 'abcd' will become 'bd', and the count is reindexed as [1, 1, 0] instead of [0, 1, 0, 1, 0, 0, ..., 0].

    @LeonCheng Thanks, means a lot.


  • 0

    Could you please explain more about the purpose of " if (((now >> i) & 1) == 1) continue; " ?
    I guess you are trying to use it to check something for every char in the target string mapping to every char from one sticker, but I am new to bit manipulation and not grasp this one of code.
    I think "now" is the following state after applying (only) one sticker to current "state" but why there is an update rule when "dp[now] > dp[state] + 1", how is it connected to above if condition to update "now"?

    Thanks very much!


  • 0

    @coder42 "if (((now >> i) & 1) == 1) continue" means "if the i-th bit of now is set, continue". At this point in our for loops, we are trying to match letters in our current sticker, to unsatisfied letters in our target. These unsatisfied letters are represented by unset bits of now.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.