Mikemirzyanov1's blog

By Mikemirzyanov1, history, 7 months ago, In English

Problem -> Problem

I am trying something similar to digit dp where we need to find the number of numbers in the range a to b satisfying some property, just in this case we have strings.

My helper function is actually calculating the number of good strings which are lexicographically less than or equal s and do not contain the substring evil.

Then I simply subtract the answer for two cases.

Please help me it's almost two weeks

Spoiler

This solution only passes 15 test cases. Help me please.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mikemirzyanov1 (previous revision, new revision, compare).

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Note that usual answer to range query $$$[L,R]$$$ dynamic-programming counting problems should be $$$dp[R]-dp[L-1]$$$. Therefore, the answer should be subtracting the results of the two cases $$$s2$$$ and $$$prev(s1)$$$, where $$$prev(s1)$$$ is the previous $$$n$$$-letter lexicographically ordered string.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a solution for this problem. Will explain in more detail in some time.

Short-explanation :-

1)First see how to count the number of strings between s1 and s2 . Let n1 = number of strings between (aaaaaaa...a and s1) , n2 = number of strings (aaaaa...aaaa and s2) , hence, answer = n2-n1+1 . (can be calculated easily with dp)

2)If you know how to do the step-1 , you will realize, that you only need to know, for each length-'i' (from aaaaa--->zzzzz(here, i = 5) , the number of strings which contains the substring "s3" atleast once, if you know it for length 'i' , transition to state 'i+1' is easy.

3)If you want the exact recurrence relations , I'll write them .

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For those who don't know about DFA I constructed a DFA for the string evil (i.e the DFA would reject all the strings which contains evil as a substring).

Then I used simple digit dp with two tights (t1,t2) for strings s1,s2 respectively and checked whether the the string is accepted by the DFA or not.

Here is my CODE it took 108ms to run(faster than all the codes submitted so far) Note the header files are missing as they are already included in leetcode's IDE.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Brownie can you help me understanding what is wrong in my approach .

    Thanks.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mikemirzyanov1 (previous revision, new revision, compare).

»
7 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

HELP

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please help me.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On this testcase:

    4
    "aaab"
    "aaba"
    "ab"
    

    You code output's 25, but the answer is 24.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mikemirzyanov1 (previous revision, new revision, compare).