算法總結 - 字元串 - 字元轉換

• 1153. String Transforms Into Another String
• 833. Find And Replace in String

1153. String Transforms Into Another String

題目連結

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

Example 1:

Input: str1 = “aabcc”, str2 = “ccdee”

Output: true

Explanation: Convert ‘c’ to ‘e’ then ‘b’ to ‘d’ then ‘a’ to ‘c’. Note that the order of conversions matter.

Example 2:

Input: str1 = “leetcode”, str2 = “codeleet”

Output: false

Explanation: There is no way to transform str1 to str2.

Note:

1 <= str1.length == str2.length <= 10^4

Both str1 and str2 contain only lowercase English letters.

Abstract

• 給出兩個字元串str1 和 str2，判斷字元串 str1 能不能在 零次 或 多次 轉化後變成 str2
• 每一次轉化時，将會一次性将 str1 中出現的所有相同字母變成其他任何小寫英文字母

Idea

用一個map記錄每個字母第一次轉化的情況，如果後續碰到同樣的字元卻發現轉化成的字母不符合map記錄的情況則說明轉化有沖突

Question to ask

• 一個字母被轉化成多個字母情況出現時該怎麼辦？
• 如果有環怎麼辦？
• 如果一個字母沒有轉化（outgoing edge）怎麼處理？

Solution

• 用一個map記錄每個字母第一次轉化的情況，如果後續碰到同樣的字元卻發現轉化成的字母不符合map記錄的情況則說明轉化有沖突

• 如果轉化可以發生，那麼必須有一個字母充當轉化的中建橋梁:
  • 比如 a -> b -> c， 字母b就是中間橋梁，是以26個字母中至少有一個字母是不會發生轉化的

Code

public boolean canConvert(String str1, String str2) {
    Map<Character, Character> map = new HashMap<>();
    
    if (str1.length() != str2.length()) return false;
    if (str1.equals(str2)) return true;
    
    Set<Character> vis = new HashSet<>();
    
    for (int i = 0; i < str1.length(); i++){
        char c1 = str1.charAt(i);
        char c2 = str2.charAt(i);
        // m1
        vis.add(c2);
        if (map.containsKey(c1)){
            if (map.get(c1) != c2){
                return false;
            }
        }else{
            map.put(c1, c2);
        }
    }
    
    return true;
}
           

Time Complexity

O (n)

Space Complexity

O(26)

Mistake

1. 沒有堅持26個字母都被轉化的情況

Summary

• 轉化和圖的問題一定要處理環

833. Find And Replace in String

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have S = “abcd” and we have some replacement operation i = 2, x = “cd”, y = “ffff”, then because “cd” starts at position 2 in the original string S, we will replace it with “ffff”.

Using another example on S = “abcd”, if we have both the replacement operation i = 0, x = “ab”, y = “eee”, as well as another replacement operation i = 2, x = “ec”, y = “ffff”, this second operation does nothing because in the original string S[2] = ‘c’, which doesn’t match x[0] = ‘e’.

All these operations occur simultaneously. It’s guaranteed that there won’t be any overlap in replacement: for example, S = “abc”, indexes = [0, 1], sources = [“ab”,“bc”] is not a valid test case.

Example 1:

Input: S = “abcd”, indexes = [0,2], sources = [“a”,“cd”], targets = [“eee”,“ffff”]

Output: “eeebffff”

Explanation: “a” starts at index 0 in S, so it’s replaced by “eee”.

“cd” starts at index 2 in S, so it’s replaced by “ffff”.

Example 2:

Input: S = “abcd”, indexes = [0,2], sources = [“ab”,“ec”], targets = [“eee”,“ffff”]

Output: “eeecd”

Explanation: “ab” starts at index 0 in S, so it’s replaced by “eee”.

“ec” doesn’t starts at index 2 in the original S, so we do nothing.

Notes:

0 <= indexes.length = sources.length = targets.length <= 100

0 < indexes[i] < S.length <= 1000

All characters in given inputs are lowercase letters.

Abstract

• 給一個字元串S，可能替換元素的位置數組indexes，需要被替換的字元串數組和替換後的字元串數組
• 判斷S在可能替換的位置是否存在可以被替換的字元串，如果有則替換成目标字元串

Idea

• 依次檢查可能替換元素的位置是否存在可替換元素并替換

Question to ask

• 由于被替換字元串的長度可能與目标字元串的長度不同，那麼怎麼確定在替換後還能跟蹤原字元的位置？

Solution

• 可以由後向前檢查S中可被替換的元素并在同時進行替換，這樣替換後字元串的長度并不會對S前半部分産生影響

Code

public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
    
    int[][] sort = new int[sources.length][2];
    
    for (int i = 0; i < indexes.length; i++){
        sort[i][0] = indexes[i];
        sort[i][1] = i;
    }
    
    
    Arrays.sort(sort, (a, b) -> b[0] - a[0]);

    int k = 0;
    
    for (int i = S.length(); i >= 0; i --){
        if (k < sort.length && i == sort[k][0]){
            String orig = sources[sort[k][1]];
            String target = targets[sort[k][1]];
            
            if (S.substring(i, i + orig.length()).equals(orig)){
                S = S.substring(0, i) + target + S.substring(i + orig.length());
            }
            k++;
        }
    }
    
    return S;
}
           

Time Complexity

O(n)

Space Complexity

O(1)

Mistake

None

Summary

• 注意逆向思維