854.K-Similar-Strings

854. K Similar Strings

题目地址

https://leetcode.com/problems/k-similar-strings/

题目描述

Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.

Given two anagrams A and B, return the smallest K for which A and B are K-similar.

Example 1:
Input: A = "ab", B = "ba"
Output: 1

Example 2:
Input: A = "abc", B = "bca"
Output: 2

Example 3:
Input: A = "abac", B = "baca"
Output: 2

Example 4:
Input: A = "aabc", B = "abca"
Output: 2
Note:

1 <= A.length == B.length <= 20
A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

代码

Approach #1 Pruned Breadth First Search

class Solution {
  public int kSimilarity(String A, String B) {
    Queue<String> queue = new ArrayDeque();
    queue.offer(A);

    Map<String, Integer> dist = new HashMap();
    dist.put(A, 0);

    while (!queue.isEmpty()) {
      String S = queue.poll();
      if (S.equals(B))    return dist.get(S);
      for (String T : getNeighbors(S, B)) {
        if (!dist.containsKey(T)) {
          dist.put(T, dist.get(S) + 1);
          queue.offer(T);
        }
      }
    }
    throw null;
  }

  public List<String> getNeighbors(String S, String target) {
    List<String> ans = new ArrayList();
    int i = 0;
    for (; i < S.length(); i++) {
      if (S.charAt(i) != target.charAt(i)) {
         break;
      }
    }

    char[] T = S.toCharArray();
    for (int j = i + 1; j < S.length(); j++) {
      if (S.charAt(j) == target.charAt(i)) {
        swap(T, i, j);
        ans.add(new String(T));
        swap(T, i, j);
      }
    }

    return ans;
  }

  public void swap(char[] T, int i, int j) {
    char tmp = T[i];
    T[i] = T[j];
    T[j] = tmp;
  }

}