LeetCode 75
Greatest Common Divisor of Strings
- Problem
- LC 1071
- Topic
- Array / String
- File
- official75_LC1071GreatestCommonDivisorOfStrings.java
- Path
- pkg5leetcode/official75/official75_LC1071GreatestCommonDivisorOfStrings.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC1071GreatestCommonDivisorOfStrings.java
- Approach
- GCD of lengths; check concatenation symmetry.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Greatest Common Divisor of Strings | LC 10715 * APPROACH: GCD of lengths; check concatenation symmetry.6 * COMPLEXITY: Time O(n), Space O(n)7 */8public class official75_LC1071GreatestCommonDivisorOfStrings {9 static String gcdOfStrings(String str1, String str2) {10 if (!(str1 + str2).equals(str2 + str1)) return "";11 return str1.substring(0, gcd(str1.length(), str2.length()));12 }13 14 static int gcd(int a, int b) {15 while (b != 0) { int t = b; b = a % b; a = t; }16 return a;17 }18 19 public static void main(String[] args) {20 check("ABC".equals(gcdOfStrings("ABCABC", "ABC")), "case1");21 check("AB".equals(gcdOfStrings("ABABAB", "ABAB")), "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}