How to Compute the Greatest Common Divisor of Strings?
- 时间:2020-09-24 11:41:27
- 分类:网络文摘
- 阅读:87 次
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.
GCD of Strings Algorithms
Let’s review the GCD algorithm for two integers, which can be illustrated in the following C++ algorithm.
1 2 3 4 | int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } |
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
A bit similar, we need to check the terminating conditions that we can get the GCD directly. Otherwise, we need to make the longer string shorter by taking off the other string from the start. Then, the problem becomes a smaller problem, which can be recursively solved.
The first version of the recursive GCD algorithm for two strings in C++ as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: string gcdOfStrings(string str1, string str2) { if (str1 == str2) { return str1; } if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) { return ""; } if (str1.size() > str2.size()) { str1 = str1.substr(str2.size()); } if (str2.size() > str1.size()) { str2 = str2.substr(str1.size()); } return gcdOfStrings(str1, str2); } }; |
class Solution { public: string gcdOfStrings(string str1, string str2) { if (str1 == str2) { return str1; } if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) { return ""; } if (str1.size() > str2.size()) { str1 = str1.substr(str2.size()); } if (str2.size() > str1.size()) { str2 = str2.substr(str1.size()); } return gcdOfStrings(str1, str2); } };
We also notice that if both strings do not contain each other, we can rewrite the string.find using a simpler logic:
1 2 3 | if (str1 + str2 != str2 + str1) { return ""; } |
if (str1 + str2 != str2 + str1) { return ""; }
For example, “123” + “123ABC” != “123ABC” + “123” and “ABC” + “ABCABC” == “ABCABC” + “ABC”. As the above recursion can be optimised using tail-recursion techniques, which can be converted to iterative while-loop.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: string gcdOfStrings(string str1, string str2) { while (true) { if (str1 + str2 != str2 + str1) { return ""; } if (str1 == str2) { return str1; } if (str1.size() > str2.size()) { str1 = str1.substr(str2.size()); } if (str2.size() > str1.size()) { str2 = str2.substr(str1.size()); } } return ""; // make compiler happy } }; |
class Solution { public: string gcdOfStrings(string str1, string str2) { while (true) { if (str1 + str2 != str2 + str1) { return ""; } if (str1 == str2) { return str1; } if (str1.size() > str2.size()) { str1 = str1.substr(str2.size()); } if (str2.size() > str1.size()) { str2 = str2.substr(str1.size()); } } return ""; // make compiler happy } };
The space complexity is O(1) constant, and the time complexity is O(M/N) where M is the length of the longer string and N is the shorter length e.g. “A”, and “AAAAAAA…”
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:WordPress官网打不开 出现 429 Too Many Request 的原因 下载更新wordpress程序及插件的方法 禁用wordpress4.4+版本自动生成768w像素缩略图功能 自动为wordpress文章图片添加alt属性和title属性 如何为WordPress导航菜单、标签、出站等链接添加nofollow标签属性 如何设置WordPress的RSS feed更新频率 利用WordPress开发者调试模式解决PHP500内部服务器错误 正确屏蔽 WordPress 版本号的代码 WordPress插件WP First Letter Avatar代码版 让WordPress文章内链接在新窗口打开的方法
- 评论列表
-
- 添加评论