6 lines in Ruby,dp with o(t.size) space, optimization of phu1ku's solution.


  • 0
    A
    def num_distinct(s,t)
      len=t.size
      prefix=[1]+[0]*len
      s.chars.each do |ch|
        len.downto(1) {|i| prefix[i]=prefix[i-1]+prefix[i] if t[i-1]==ch}
      end
      prefix[-1]
    end
    

    thanks to phu1ku.


Log in to reply
 

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