用另一個子字串替換字串中的兩個子字串

---

給定三個字串 S、A 和 B。您必須將等於 A 的 S 的每個子字串替換為 B，並將等於 B 的 S 的每個子字串替換為 A。可能存在兩個或多個匹配 A 或 B 的子字串重疊。為了避免對這種情況的混淆，您必須找到匹配 A 或 B 的最左邊的子字串，將其替換，然後繼續處理字串的其餘部分。

輸入

S = “aab”, A = “aa”, B = “bb” 

輸出

“bbb” 

將前兩個字元與 A 匹配並將其替換為 B，我們得到“bbb”。然後從索引 3 開始繼續演算法，我們找不到更多匹配項。

輸入

S = “aabbaabb”, A = “aa”, B = “bb” 

輸出

“bbaabbaa” 

將所有出現的“aa”替換為“bb”，“bb”替換為“aa”，因此最終字串為“bbaabbaa”。

解決方案

目標是在字串 S 中發現匹配 A 或 B 的最左邊的子字串。當 A 和 B 都位於同一索引處時，首先更改匹配 A 的子字串。然後將不匹配的子字串新增到結果中，並重復此過程，直到找不到更多匹配項。如果沒有發現更多匹配項，則將最終子字串新增到最終結果中。

此演算法的時間複雜度為 O(N*M)，其中 N 是字串 S 的長度，M 是字串 A 和 B 的長度。在最壞的情況下，我們可能必須遍歷整個字串 S 才能找到每個匹配項。由於我們至少必須分析字串中的每個字元一次，因此這也是理想的時間複雜度。

Java 實現

讓我們看看 Java 實現

示例

public class ReplaceSubstring {
	 //method to replace string
    public static String replaceSubstring(String S, String A, String B) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < S.length()) {
            // Find the leftmost sub-string that matches A or B
            int aIndex = S.indexOf(A, i);
            int bIndex = S.indexOf(B, i);
            if (aIndex == -1 && bIndex == -1) {
                // No more matches found
                sb.append(S.substring(i));
                break;
            } else if (aIndex == -1 || (bIndex != -1 && bIndex < aIndex)) {
                // Replace the sub-string matching B
                sb.append(S.substring(i, bIndex)).append(A);
                i = bIndex + B.length();
            } else {
                // Replace the sub-string matching A
                sb.append(S.substring(i, aIndex)).append(B);
                i = aIndex + A.length();
            }
        }
        return sb.toString();
    }
	 //Driver method
    public static void main(String[] args) {
        String S = "aabbcc";
        String A = "aa";
        String B = "bb";
        String result = replaceSubstring(S, A, B);
        System.out.println(result);
    }
}

輸出

bbaacc

替代方法

我們前面介紹的方法的時間複雜度為 O(N*M)，其中 N 是字串 S 的長度，M 是字串 A 和 B 的長度。這已經是最佳時間複雜度，因為我們需要至少檢查字串的每個字元一次。

但是，我們可以透過使用 **StringBuilder** 來構建結果字串（而不是重複連線子字串）來最佳化實現。我們還可以透過手動迭代字串並比較子字串來避免使用 indexOf() 來搜尋下一個匹配項。以下是使用這些最佳化的更新後的實現

示例

public class ReplaceSubstring {
	//method to replace string
    public static String replaceSubstring(String S, String A, String B) {
        StringBuilder sb = new StringBuilder(S.length());
        int i = 0;
        while (i < S.length()) {
            // Check if the current substring matches A
            if (i + A.length() <= S.length() && S.substring(i, i + A.length()).equals(A)) {
                sb.append(B);
                i += A.length();
            }
            // Check if the current substring matches B
            else if (i + B.length() <= S.length() && S.substring(i, i + B.length()).equals(B)) {
                sb.append(A);
                i += B.length();
            }
            // Current substring does not match A or B
            else {
                sb.append(S.charAt(i));
                i++;
            }
        }
        return sb.toString();
    }
	
	//Driver method
    public static void main(String[] args) {
        String S = "aabbcc";
        String A = "aa";
        String B = "bb";
        String result = replaceSubstring(S, A, B);
        System.out.println(result);
    }
}

輸出

bbaacc

此實現與之前的實現具有相同的時間複雜度，但由於減少了字串連線和 indexOf 呼叫的開銷，因此在實踐中可能更快。