Commit00125b7

committed

Create 1071-greatest-common-divisor-of-strings.java

1 parentd642910 commit00125b7Copy full SHA for 00125b7

File tree

+27

-0

lines changed

+27

-0

lines changed

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+classSolution {`
	`2`	`+`
	`3`	`+// Helper function to calculate gcd using Euclidean algorithm`
	`4`	`+publicintgcd(inta,intb){`
	`5`	`+if(b ==0){`
	`6`	`+returna;`
	`7`	`+ }`
	`8`	`+returngcd(b,a%b);`
	`9`	`+ }`
	`10`	`+`
	`11`	`+/*`
	`12`	`+ Approach: If the string have a GCD, then str1 will be of the form mGCD and str2 will be of the form nGCD.`
	`13`	`+ So, str1 + str2 = mGCD + nGCD = (m+n)*GCD, hence str1 + str2 should be equal to str2 + str1.`
	`14`	`+ If the above condition is satisfied, then we can find the GCD of the lengths of the strings and return the substring of str1 of length GCD.`
	`15`	`+ Else, return empty string.`
	`16`	`+ */`
	`17`	`+`
	`18`	`+publicStringgcdOfStrings(Stringstr1,Stringstr2) {`
	`19`	`+if((str1 +str2).equals(str2 +str1)){`
	`20`	`+intlen1 =str1.length();`
	`21`	`+intlen2 =str2.length();`
	`22`	`+intgcd =gcd(len1,len2);`
	`23`	`+returnstr1.substring(0,gcd);`
	`24`	`+ }`
	`25`	`+return"";`
	`26`	`+ }`
	`27`	`+}`

Comments

(0)