Commit7ed10fd

authored

correct space complexity and simple code

1 parent0024d62 commit7ed10fdCopy full SHA for 7ed10fd

File tree

+47

-45

lines changed

+47

-45

lines changed

Lines changed: 14 additions & 11 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,23 +1,26 @@`
`1`	`1`	`#include<unordered_map>`
`2`	`2`	`#include<string>`
`3`		`-usingnamespacestd;`
`4`	`3`
`5`	`4`	`classSolution {`
`6`	`5`	`public:`
`7`		`-boolcanConstruct(string ransomNote, string magazine) {`
`8`		`- unordered_map<char,int>counter;`
`9`		`-`
`10`		`-for (charc : magazine) {`
`11`		`-counter[c]++;`
	`6`	`+boolcanConstruct(std::string ransomNote,std::string magazine) {`
	`7`	`+std::unordered_map<char,int>hashmap;`
	`8`	`+`
	`9`	`+for (charch : magazine) {`
	`10`	`+hashmap[ch]++;`
`12`	`11`	`}`
`13`		`-`
`14`		`-for (char c : ransomNote) {`
`15`		`-if (counter[c] ==0) {`
	`12`	`+`
	`13`	`+for (char ch : ransomNote) {`
	`14`	`+if (hashmap[ch] >0) {`
	`15`	`+ hashmap[ch]--;`
	`16`	`+ }else {`
`16`	`17`	`returnfalse;`
`17`	`18`	`}`
`18`		`- counter[c]--;`
`19`	`19`	`}`
`20`		`-`
	`20`	`+`
`21`	`21`	`returntrue;`
`22`	`22`	`}`
`23`	`23`	`};`
	`24`	`+`
	`25`	`+// Time Complexity: O(m + n) -> m = length of ransomNote, n = length of magazine`
	`26`	`+// Space Complexity: O(n) -> we're using an unordered_map`

Lines changed: 12 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,20 +1,24 @@`
`1`	`1`	`importjava.util.HashMap;`
`2`	`2`
`3`		`-publicclassSolution {`
	`3`	`+classSolution {`
`4`	`4`	`publicbooleancanConstruct(StringransomNote,Stringmagazine) {`
`5`		`-HashMap<Character,Integer>counter =newHashMap<>();`
	`5`	`+HashMap<Character,Integer>hashmap =newHashMap<>();`
`6`	`6`
`7`		`-for (charc :magazine.toCharArray()) {`
`8`		`-counter.put(c,counter.getOrDefault(c,0) +1);`
	`7`	`+for (charch :magazine.toCharArray()) {`
	`8`	`+hashmap.put(ch,hashmap.getOrDefault(ch,0) +1);`
`9`	`9`	`}`
`10`		`-`
`11`		`-for (charc :ransomNote.toCharArray()) {`
`12`		`-if (!counter.containsKey(c) \|\|counter.get(c) ==0) {`
	`10`	`+`
	`11`	`+for (charch :ransomNote.toCharArray()) {`
	`12`	`+if (hashmap.getOrDefault(ch,0) >0) {`
	`13`	`+hashmap.put(ch,hashmap.get(ch) -1);`
	`14`	`+ }else {`
`13`	`15`	`returnfalse;`
`14`	`16`	`}`
`15`		`-counter.put(c,counter.get(c) -1);`
`16`	`17`	`}`
`17`	`18`
`18`	`19`	`returntrue;`
`19`	`20`	`}`
`20`	`21`	`}`
	`22`	`+`
	`23`	`+// Time Complexity: O(m + n) -> m = len(ransomNote), n = len(magazine)`
	`24`	`+// Space Complexity: O(n) -> we're using a hashmap`

Lines changed: 15 additions & 11 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,16 +1,20 @@`
`1`		`-functioncanConstruct(ransomNote,magazine){`
`2`		`-constcounter={};`
`3`		`-`
`4`		`-for(constcofmagazine){`
`5`		`-counter[c]=(counter[c]\|\|0)+1;`
	`1`	`+varcanConstruct=function(ransomNote,magazine){`
	`2`	`+lethashmap={};`
	`3`	`+`
	`4`	`+for(letchofmagazine){`
	`5`	`+hashmap[ch]=(hashmap[ch]\|\|0)+1;`
`6`	`6`	`}`
`7`		`-`
`8`		`-for(constcofransomNote){`
`9`		`-if(!counter[c]\|\|counter[c]===0){`
	`7`	`+`
	`8`	`+for(letchofransomNote){`
	`9`	`+if(hashmap[ch]>0){`
	`10`	`+hashmap[ch]--;`
	`11`	`+}else{`
`10`	`12`	`returnfalse;`
`11`	`13`	`}`
`12`		`-counter[c]--;`
`13`	`14`	`}`
`14`		`-`
	`15`	`+`
`15`	`16`	`returntrue;`
`16`		`-}`
	`17`	`+};`
	`18`	`+`
	`19`	`+// Time Complexity: O(m + n) -> m = length of ransomNote, n = length of magazine`
	`20`	`+// Space Complexity: O(n) -> we're using a hashmap`

Lines changed: 6 additions & 15 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,22 +1,13 @@`
`1`	`1`	`classSolution:`
`2`	`2`	`defcanConstruct(self,ransomNote:str,magazine:str)->bool:`
`3`		`-counter={}`
	`3`	`+hashmap=Counter(magazine)# TC for Counter is O(n)`
`4`	`4`
`5`		`-forcinmagazine:`
`6`		`-ifcincounter:`
`7`		`-counter[c]+=1`
	`5`	`+forchinransomNote:`
	`6`	`+ifhashmap[ch]>0:`
	`7`	`+hashmap[ch]-=1`
`8`	`8`	`else:`
`9`		`-counter[c]=1`
`10`		`-`
`11`		`-forcinransomNote:`
`12`		`-ifcnotincounter:`
`13`	`9`	`returnFalse`
`14`		`-elifcounter[c]==1:`
`15`		`-delcounter[c]`
`16`		`-else:`
`17`		`-counter[c]-=1`
`18`		`-`
`19`	`10`	`returnTrue`
`20`	`11`
`21`		`-# Time Complexity: O(m + n)`
`22`		`-# Space Complexity: O(1)`
	`12`	`+# Time Complexity: O(m + n) -> m = len(ransomNote), n = len(magazine)`
	`13`	`+# Space Complexity: O(n) -> we're using a hashmap`

Comments

(0)