Commit3a5138e

committed

Ruby Solution for Minimum Window Substring

1 parenteff3535 commit3a5138eCopy full SHA for 3a5138e

File tree

+41

-0

lines changed

+41

-0

lines changed

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+`
	`2`	`+defmin_window(s,t)`
	`3`	`+`
	`4`	`+return""ift ==""`
	`5`	`+count_t=Hash.new(0)`
	`6`	`+window=Hash.new(0)`
	`7`	`+`
	`8`	`+t.each_chardo \|c\|`
	`9`	`+count_t[c] +=1`
	`10`	`+end`
	`11`	`+`
	`12`	`+have=0`
	`13`	`+need=count_t.length`
	`14`	`+`
	`15`	`+res=[-1,-1]`
	`16`	`+result_length=9999999999`
	`17`	`+l=0`
	`18`	`+(0..s.length-1).eachdo \|r\|`
	`19`	`+c=s[r]`
	`20`	`+window[c] +=1`
	`21`	`+`
	`22`	`+have +=1if((count_t.keys.include?(c)) &&(window[c] ==count_t[c]))`
	`23`	`+while(have ==need)`
	`24`	`+if(r-l+1) <result_length`
	`25`	`+res=[l,r]`
	`26`	`+result_length=(r-l+1)`
	`27`	`+`
	`28`	`+end`
	`29`	`+window[s[l]] -=1`
	`30`	`+have -=1if((count_t.keys.include?(s[l])) &&(window[s[l]] <count_t[s[l]]))`
	`31`	`+l +=1`
	`32`	`+end`
	`33`	`+end`
	`34`	`+l=res[0]`
	`35`	`+r=res[1]`
	`36`	`+ifresult_length !=9999999999`
	`37`	`+returns[l..r]`
	`38`	`+else`
	`39`	`+return""`
	`40`	`+end`
	`41`	`+end`

Comments

(0)