854. 相似度為 K 的字元串 : 正常搜尋運用題

題目描述

這是 LeetCode 上的 ​​854. 相似度為 K 的字元串​​ ，難度為 困難。

Tag : 「啟發式搜尋」、「AStar 算法」

對于某些非負整數 ​

​k​

​​ ，如果交換 中兩個字母的位置恰好 ​​

​k​

​​ 次，能夠使結果字元串等于 ，則認為字元串 和 的 相似度為 ​​

​k​

​ 。

給你兩個字母異位詞 和 ，傳回 和 的相似度 ​​

​k​

​ 的最小值。

示例 1：

輸入：s1 = "ab", s2 = "ba"      

示例 2：

輸入：s1 = "abc", s2 = "bca"      

提示：

• ​

  ​s1​

  ​​ 和​

  ​s2​

  ​​  隻包含集合​

  ​{'a', 'b', 'c', 'd', 'e', 'f'}​

  ​ 中的小寫字母
• ​

  ​s2​

  ​​ 是​

  ​s1​

  ​ 的一個字母異位詞

AStar 算法

問題本質為将 ​

​s1​

​​ 轉換為 ​

​s2​

​​ 的最小操作次數，由于題目確定了 ​

​s1​

​​ 和 ​

​s2​

​ 互為字母異位詞（必然有解），是以最好的求解方式是使用 AStar 算法。

可直接根據本題規則來設計 AStar 的啟發式函數: 對于兩個狀态 ​

​a​

​​ 和 ​

​b​

​ 直接計算出「理論最小轉換次數」: 不同字元串的轉換成本之和，由于每一次交換最多可減少兩個不同的字元，我們可計算 ​

​a​

​ 與 ​

​b​

​ 的不同字元數量 ，對應的理論最小轉換次數為 。

需要注意的是：由于我們衡量某個字元 ​

​str​

​ 的估值是以目标字元串 ​

​target​

​ 為基準，是以我們隻能確定 ​

​target​

​ 出隊時為「距離最短」，而不能確定中間節點出隊時「距離最短」，是以我們不能單純根據某個節點是否「曾經入隊」而決定是否入隊，還要結合目前節點的「最小距離」是否被更新而決定是否入隊。

一些細節：在使用目前狀态（字元串）​

​poll​

​​ 拓展新狀态（字元串）​

​nstr​

​ 時，隻拓展能夠減少不同字元數量的方案，進而收窄搜尋空間。

Java 代碼：

class Solution {
    int n;
    String t;
    int f(String s) {
        int ans = 0;
        for (int i = 0; i < n; i++) ans += s.charAt(i) != t.charAt(i) ? 1 : 0;
        return ans + 1 >> 1;
    }
    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) return 0;
        t = s2;
        n = s1.length();
        Map<String, Integer> map = new HashMap<>();
        PriorityQueue<String> pq = new PriorityQueue<>((a,b)->{
            int v1 = f(a), v2 = f(b), d1 = map.get(a), d2 = map.get(b);
            return (v1 + d1) - (v2 + d2);
        });
        map.put(s1, 0);
        pq.add(s1);
        while (!pq.isEmpty()) {
            String poll = pq.poll();
            int step = map.get(poll);
            char[] cs = poll.toCharArray();
            int idx = 0;
            while (idx < n && cs[idx] == t.charAt(idx)) idx++;
            for (int i = idx + 1; i < n; i++) {
                if (cs[i] == t.charAt(idx) && cs[i] != t.charAt(i)) {
                    swap(cs, idx, i);
                    String nstr = String.valueOf(cs);
                    if (map.containsKey(nstr) && map.get(nstr) <= step + 1) continue;
                    if (nstr.equals(t)) return step + 1;
                    map.put(nstr, step + 1);
                    pq.add(nstr);
                    swap(cs, idx, i);
                }
            }
        }
        return -1; // never
    }
    void swap(char[] cs, int i, int {
        char c =      

• 時間複雜度：啟發式搜尋不分析時空複雜度
• 空間複雜度：啟發式搜尋不分析時空複雜度

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.854​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。