今天解決了LeetCode 75系列的第二題。我想分享一下我是如何解決這個問題的。
問題陳述:
給定兩個字串,str1 和 str2。傳回最大的字串 x,使得 x 可以整除 str1 和 str2。
範例:
輸入:str1 = "ABCABC", str2 = "ABC"
輸出:“ABC”
輸入:str1 = "ABABAB", str2 = "ABAB"
輸出:“AB”
輸入:str1 =“LEET”,str2 =“CODE”
輸出:“”
**
我的方法**
我將解決方案分為三個部分:
檢查公約數字串是否存在:
首先,我透過連接 str1 str2 和 str2 str1 來檢查是否存在公約數。
如果連接的兩個字串不相等,則表示沒有公約數,函數會傳回空字串 ("")。
求 GCD 長度:
接下來,我求 str1 和 str2 長度的 GCD。
我使用遞歸 gcd() 函數。如果 b !== 0,則函數使用兩個參數遞歸呼叫自身:
gcd(a, b) = gcd(b, a % b)
一旦 b = 0,函數傳回 a,即 GCD 長度。
計算範例:
初始呼叫: gcd(6, 3)
由於 b = 3 不為 0,因此遞歸呼叫 gcd(3, 6 % 3) → gcd(3, 0)
第二次呼叫: gcd(3, 0)
現在 b = 0,因此函數傳回 3。
提取 GCD 子字串:
最後,我使用 gcdlength 從 str1 中提取子字串。
function gcdOfStrings(str1, str2) { // recursive function to calculate the GCD of two numbers function gcd(a, b) { console.log(a, b); return b === 0 ? a : gcd(b, a % b); } // Step 1: Check if str1 and str2 match or not if (str1 + str2 !== str2 + str1) { return ""; // No common pattern exists } // Step 2: Find the GCD of the lengths of str1 and str2 const len1 = str1.length; const len2 = str2.length; const gcdLength = gcd(len1, len2); // Step 3: The largest divisor substring return str1.substring(0, gcdLength); } // Example usage: console.log(gcdOfStrings("ABCABC", "ABC")); // Output: "ABC" console.log(gcdOfStrings("ABABAB", "ABAB")); // Output: "AB" console.log(gcdOfStrings("LEET", "CODE")); // Output: ""
如果您有更好的解決方案或想法,請隨時與我分享。
以上是JavaScript 中字串的最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章!