[牛客題霸-高頻演算法面試題]字串距離計算-有解無憂

題目描述

給定兩個長度相等的，由小寫字母組成的字串S1和S2，定義S1和S2的距離為兩個字串有多少個位置上的字母不相等，

現在牛牛可以選定兩個字母X1和X2，將S1中的所有字母X1均替換成X2，（X1和X2可以相同）

牛牛希望知道執行一次替換之后，兩個字串的距離最少為多少，

示例1

輸入："aaa","bbb"

輸出：0

說明：牛牛可以將S1中的字符'a'全部替換成字符'b'，這樣S1就變成了"bbb"，那么S1和S2的距離就是0

示例2

輸入："aabb","cdef"

輸出：3

說明：一種可行的方案是將S1中的字符'a'全部替換成字符'c'，那么S1變成了"ccbb"，和S2的距離是3

思路

使用字典count[26][26]記錄S1、S2中的字符對，count[X1][X2]表示S1和S2中相同位置的字符對個數，即有多少個i使得S1[i]==X1,S2[i]==X2成立，這個值掃描一遍字串即可得到；掃描的同時記錄替換前的原始距離origin，然后列舉所有可能的X1、X2，此時的距離為origin+count[X1][X1]-count[X1][X2]，用一個變數min來保存結果，每次列舉時進行更新，

origin+count[X1][X1]-count[X1][X2]這個式子可能比較難理解，沒關系，我們舉個例子：

現在給出兩個字串aabbcb和aacbec，第一次遍歷字串的時候，可以依次得到6個字符對，根據字符對個數，對count陣列初始化；同時根據題干中的定義：距離為兩個字串有多少個位置上的字母不相等，我們可以得到origin=3，也就是圖中連線的3個字符對：b-c、c-e、b-c

列舉的時候，我們以X1=b、X2=c為例，也就是將S1中的所有字母b均替換成c（圖中紅色標記的c為替換的字符），對比上下兩個S1、S2，我們可以發現這次替換的影響范圍是S1中原來為b的位置并且S2中該位置的字符是c或b，也就是說對a-a和c-e這兩個字符對是不產生影響的（如果存在類似于b-a、b-d這樣的字符對也是不影響的，因為替換后c-a、c-d依然包含在origin中），

那么來看影響范圍內的字符對：b-c和b-b，替換后變成了c-c和c-b，這時產生了一個新的可以算入距離的字符對c-b（圖中紅線連接處），同時c-c不符合距離的定義，要從原始距離中刨去（圖中打叉的地方），有多少個需要算入和刨去的字符對呢？因為count陣列記錄的是替換前的狀態，所以就要看這些字符對是由誰“變”來的：新算入的字符對原來是X1-X1，刨去的字符對原來是X1-X2，所以新的距離為origin+count[X1][X1]-count[X1][X2]

JAVA代碼

public class Solution {
    /**
     * 計算最少的距離
     * @param S1 string字串 第一個字串
     * @param S2 string字串 第二個字串
     * @return int整型
     */
    public int GetMinDistance (String S1, String S2) {
        int[][] count = new int[26][26];
        int origin = 0;
        for(int i = 0; i < S1.length(); i++) {
            char ch1 = S1.charAt(i), ch2 = S2.charAt(i);
            count[ch1 - 'a'][ch2 - 'a'] ++;
            if(ch1 != ch2) origin++;
        }
        int min = S1.length();
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < 26; j++) {
                min = Math.min(min, origin + count[i][i] - count[i][j]);
            }
        }
        return min;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21209.html

標籤：其他

上一篇：【葵花寶典@2020Python面試】

下一篇：面試官不是你想吊打就能吊打的