aboutsummaryrefslogtreecommitdiff
path: root/greatest_common_div_string.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'greatest_common_div_string.cpp')
-rw-r--r--greatest_common_div_string.cpp36
1 files changed, 36 insertions, 0 deletions
diff --git a/greatest_common_div_string.cpp b/greatest_common_div_string.cpp
new file mode 100644
index 0000000..420eb10
--- /dev/null
+++ b/greatest_common_div_string.cpp
@@ -0,0 +1,36 @@
+// 1071. Greatest Common Divisor of Strings
+#include "leetcode.h"
+
+/*
+ * for two strings 's' & 't', we say 't' divides 's' if and only if s = t + ...
+ * + t ie. 't' is concatenated with itself one or more times given two strings
+ * 'str1' & 'str2', return largest string 'x' such that 'x' divides both 'str1'
+ * & 'str2'
+ */
+
+class Solution {
+public:
+ string gcdOfStrings(string str1, string str2) {
+ /* first check if finding gcd is even possible
+ * eg. ABAB + AB == AB + ABAB
+ * LEET + CODE != CODE + LEET
+ */
+ if (str1 + str2 == str2 + str1) {
+ // get gcd of string sizes
+ // eg. ABAB (4) and AB (2), gcd = 2
+ int gcd = __gcd(str1.size(), str2.size());
+ // return substring of (either) string
+ // beginning at element 0 and a length of gcd
+ return str1.substr(0, gcd);
+ // if gcd isn't possible, return empty string
+ } else
+ return "";
+ }
+};
+
+int main() {
+ Solution obj;
+ cout << obj.gcdOfStrings("ABCABC", "ABC") << endl; // expect: ABC
+ cout << obj.gcdOfStrings("ABABAB", "ABAB") << endl; // expect: AB
+ cout << obj.gcdOfStrings("LEET", "CODE") << endl; // expect: n/a
+}