LeetCode 1071. Greatest Common Divisor of Strings (Java版; Easy)

àì夳堔傛蜴生んèń 2023-07-13 15:11 21阅读 0赞

### [welcome to my blog][] ###

## LeetCode 1071. Greatest Common Divisor of Strings (Java版; Easy) ##

#### 题目描述 ####

For strings S and T, we say "T divides S" if and only if S = T + ... + T  (T concatenated with itself 1 or more times)
    
    Return the largest string X such that X divides str1 and X divides str2.
    
     
    
    Example 1:
    
    Input: str1 = "ABCABC", str2 = "ABC"
    Output: "ABC"
    Example 2:
    
    Input: str1 = "ABABAB", str2 = "ABAB"
    Output: "AB"
    Example 3:
    
    Input: str1 = "LEET", str2 = "CODE"
    Output: ""
     
    
    Note:
    
    1 <= str1.length <= 1000
    1 <= str2.length <= 1000
    str1[i] and str2[i] are English uppercase letters.

#### 第一次做; 暴力; 核心:1)如果两个字符串str1和str2的最大公因字符串是s, 设该字符串长度为n, 那么str1.substring(0,n)一定等于s, str2.substring(0,n)一定等于s ####

class Solution { 
        public String gcdOfStrings(String str1, String str2) { 
            //暴力
            int n1 = str1.length(), n2 = str2.length();
            int min = Math.min(n1, n2);
            for(int i=min; i>=1; i--){ 
                //当前长度既是n1的因数又是n2的因数时判断是否是gcd; tip:这里的i其实是n1和n2的因数, 但不一定是最大公因数
                if(n1%i==0 && n2%i==0){ 
                    boolean flag = check(str1, str2.substring(0,i)) && check(str2, str1.substring(0,i));
                    if(flag)
                        return str1.substring(0,i);
                }
            }
            return "";
        }
    
        private boolean check(String str, String s){ 
            int n = str.length()/s.length();
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<n; i++){ 
                sb.append(s);
            }
            return sb.toString().equals(str);
        }
    }

#### 第一次做; 直接看的题解; 数学法, 数学才是王道啊! ####

class Solution { 
        public String gcdOfStrings(String str1, String str2) { 
            if(!(str1+str2).equals(str2+str1))
                return "";
            return str1.substring(0, gcd(str1.length(), str2.length()));
        }
    
        private int gcd(int a, int b){ 
            return b==0? a : gcd(b, a%b);
        }
    }

#### 最大公因数的求法, 辗转相除法, 核心: 1)辗转 2)取模 ####

//递归版
    private int gcd(int a, int b){ 
        return b==0? a: gcd(b, a%b);
    }
    
    //迭代版
    private int gcd(int a, int b){ 
           while(b != 0){ 
               int tmp = b;
               b = a%b;
               a = tmp;
           }
           return a;
       }
       
    /* 12 9 3 9 3 3 3 0 3 12 7 1 7 5 1 5 2 1 2 1 1 1 0 1 */

[welcome to my blog]: https://littlehaes.com