leetcode1071 字符串的最大公因子

题目详情

题目解析

解法一 ： 暴力法

1. 定义函数 boolean isgcdOfString(String str, String gcd) 用来 str 是否能被 gcd 整除
2. 定义函数 Set< String> divOfString(String str) 返回所有能整除字符串 str 的字符串
3. 对两个字符串 str1 和 str2 分别求能整除各自的字符串集合，然后找出并返回两个集合中长度最大的字符串 即为最终的两个字符串的最大公因子

import java.util.HashSet;
import java.util.Set;public class Solution {public String gcdOfStrings(String str1, String str2){if(str1.length() == 0 || str2.length() == 0)return "";Set<String> gcdOfStr1 = divOfString(str1);Set<String> gcdOfStr2 = divOfString(str2);int max = 0;String res = "";for(String gcd : gcdOfStr1){if(gcdOfStr2.contains(gcd) && max < gcd.length()){res = gcd;max = gcd.length();}}return res;}private Set<String> divOfString(String str){Set<String> res = new HashSet<>();for(int i = 0; i <= str.length(); i ++){String gcd = str.substring(0, i);if(isgcdOfString(str, gcd))res.add(gcd);}return res;}private boolean isgcdOfString(String str, String gcd){int m = str.length();int n = gcd.length();if(n == 0)return true;if(m % n != 0)return false;int start = 0;int end = n;while(end <= m){if(!(str.substring(start, end)).equals(gcd))return false;start = end;end += n;}return true;}
}

解法二 ： 暴力法（改进）

对两字符串中长度较短的字符串依次遍历 String gcd = str.substring(0, i) ，判断gcd是否为 str1 和 str2 的公因子，找出最大的公因子。

public class Solution2 {public String gcdOfStrings(String str1, String str2){int m = str1.length();int n = str2.length();for(int i = Math.min(m, n); i > 0; i --){if(m % i == 0 && n % i == 0) {String gcd = str1.substring(0, i);if(isgcdOfString(str1, gcd) && isgcdOfString(str2, gcd))return gcd;}}return "";}private boolean isgcdOfString(String str, String gcd){if(gcd.length() == 0)return true;int lenX = str.length() / gcd.length();String ans = "";for(int i = 0; i < lenX; i ++){ans += gcd;}return str.equals(ans);}
}

解法三

定理：如果str1 + str2 == str2 + str1, 则有两个字符串的最大公因子的长度为 str1.length() 和 str2.length() 的最大公约数
根据上述的定理可以直接通过判断str1 + str2 == str2 + str1 若为false , 返回 “” ; 若为true， 返回 str1.substring( gcd(str1.length(), str2.length()) )

public class Solution3 {public String gcdOfStrings(String str1, String str2){if(!(str1 + str2).equals(str2 + str1))return "";int gcd = gcd(str1.length(), str2.length());return str1.substring(0, gcd);}/*** 求最大公约数* @param m* @param n* @return*/private int gcd(int m, int n){int gcd = 1;if(m < n){  //交换两个数的位置，m = m + n;n = m - n;m = m - n;}if(m % n == 0)return n;while(m % n != 0){m = m % n;if(m < n){m = m + n;n = m - n;m = m - n;}if(m % n == 0)gcd = n;}return n;}
}