递归回溯法，求解《854. 相似度为 K 的字符串》

var kSimilarity = function(s1, s2) {
  const n = s1.length, a1 = s1.split('')
  let r = Number.MAX_SAFE_INTEGER
  ;(function d (i, k) {
    if (i === n) return r = Math.min(r, k)
    if (a1[i] === s2[i]) return d(i + 1, k)
    if (k + needSwap(a1, s2, i + 1, n) >= r) return
    for (let j = i + 1; j < n; j++) {
      if (a1[j] === s2[i]) {
        swap(a1, i, j)
        d(i + 1, k + 1)
        swap(a1, i, j)
      }
    }
  })(0, 0)
  return r
};
const swap = (nums, a, b) => [nums[a], nums[b]] = [nums[b], nums[a]]
const needSwap = (a1, s2, start, n) => {
  let need = 0
  for (let i = start; i < n; i++) if (a1[i] !== s2[i]) need++
  return need >> 1
}

function kSimilarity(s1: string, s2: string): number {
  const n = s1.length, a1: string[] = Array.from(s1)
  let r = Number.MAX_SAFE_INTEGER
  ;(function d (i, k) {
    if (i === n) return r = Math.min(r, k)
    if (a1[i] === s2[i]) return d(i + 1, k)
    if (k + needSwap(a1, s2, i + 1, n) >= r) return
    for (let j = i + 1; j < n; j++) {
      if (a1[j] === s2[i]) {
        swap(a1, i, j)
        d(i + 1, k + 1)
        swap(a1, i, j)
      }
    }
  })(0, 0)
  return r
};
const swap = (nums: string[], a: number, b: number) => {
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}
const needSwap = (a1: string[], s2: string, start: number, n: number) => {
  let need = 0
  for (let i = start; i < n; i++) if (a1[i] !== s2[i]) need++
  return need >> 1
}

class Solution {
  private $r = PHP_INT_MAX, $n, $a1, $s2;
  function kSimilarity($s1, $s2) {
    $this->n = strlen($s1);
    $this->a1 = str_split($s1);
    $this->s2 = $s2;
    $this->d(0, 0);
    return $this->r;
  }
  function d($i, $k) {
    if ($i === $this->n) return $this->r = min($this->r, $k);
    if ($this->a1[$i] === $this->s2[$i]) return $this->d($i + 1, $k);
    if ($k + $this->needSwap($i + 1) >= $this->r) return;
    for ($j = $i + 1; $j < $this->n; $j++) {
      if ($this->a1[$j] === $this->s2[$i]) {
        $this->swap($i, $j);
        $this->d($i + 1, $k + 1);
        $this->swap($i, $j);
      }
    }
  }
  function swap($a, $b) {
    list($this->a1[$a], $this->a1[$b]) = array($this->a1[$b], $this->a1[$a]);
  }
  function needSwap($start) {
    $need = 0;
    for ($i = $start; $i < $this->n; $i++) {
      if ($this->a1[$i] !== $this->s2[$i]) $need++;
    }
    return $need >> 1;
  }
}

func kSimilarity(s1 string, s2 string) int {
  n, b1, r := len(s1), []byte(s1), int(^uint(0) >> 1)
  var needSwap func(start int) int
  needSwap = func(start int) int {
    need := 0
    for i := start; i < n; i++ {
      if b1[i] != s2[i] {
        need++
      }
    }
    return need >> 1
  }
  var d func (i int, k int)
  d = func(i int, k int) {
    if i == n {
      r = min(r, k)
      return
    }
    if b1[i] == s2[i] {
      d(i + 1, k)
    }
    if k + needSwap(i + 1) >= r {
      return
    }
    for j := i + 1; j < n; j++ {
      if (b1[j] == s2[i]) {
        swap(b1, i, j)
        d(i + 1, k + 1)
        swap(b1, i, j)
      }
    }
  }
  d(0, 0)
  return r
}
func swap(bs []byte, a int, b int) {
  bs[a], bs[b] = bs[b], bs[a]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

class Solution {
  private int r = Integer.MAX_VALUE;
  private int n;
  private String s2;
  private char[] c1;
  public int kSimilarity(String s1, String s2) {
    n = s1.length();
    c1 = s1.toCharArray();
    this.s2 = s2;
    d(0, 0);
    return r;
  }
  public void d(int i, int k) {
    if (i == n) {
      r = Math.min(r, k);
      return;
    }
    if (c1[i] == s2.charAt(i)) {
      d(i + 1, k);
      return;
    }
    if (k + needSwap(i + 1) >= r) return;
    for (int j = i + 1; j < n; j++) {
      if (c1[j] == s2.charAt(i)) {
        swap(i, j);
        d(i + 1, k + 1);
        swap(i, j);
      }
    }
  }
  public void swap(int a, int b) {
    char t = c1[a];
    c1[a] = c1[b];
    c1[b] = t;
  }
  public int needSwap(int start) {
    int need = 0;
    for (int i = start; i < n; i++) if (c1[i] != s2.charAt(i)) need++;
    return need >> 1;
  }
}

public class Solution {
  private int n;
  private int r = int.MaxValue;
  private char[] c1;
  private string s2;
  public int KSimilarity(string s1, string s2) {
    this.n = s1.Length;
    this.s2 = s2;
    c1 = s1.ToCharArray();
    d(0, 0);
    return r;
  }
  public void d(int i, int k) {
    if (i == n) {
      r = Math.Min(r, k);
      return;
    }
    if (c1[i] == s2[i]) {
      d(i + 1, k);
      return;
    }
    if (k + needSwap(i + 1) >= r) return;
    for (int j = i + 1; j < n; j++) {
      if (c1[j] == s2[i]) {
        swap(i, j);
        d(i + 1, k + 1);
        swap(i, j);
      }
    }
  }
  public void swap(int a, int b) {
    char t = c1[a];
    c1[a] = c1[b];
    c1[b] = t;
  }
  public int needSwap(int start) {
    int need = 0;
    for (int i = start; i < n; i++) {
      if (c1[i] != s2[i]) need++;
    }
    return need >> 1;
  }
}

#define MIN(a, b) (a < b ? a : b)
void swap(char* s1, int a, int b) {
  char t = s1[a];
  s1[a] = s1[b];
  s1[b] = t;
}
int needSwap(int start, char* s1, char* s2, int n) {
  int need = 0;
  for (int i = start; i < n; i++) if (s1[i] != s2[i]) need++;
  return need >> 1;
}
void d(int i, int k, char* s1, char* s2, int n, int* r) {
  if (i == n) {
    *r = MIN(*r, k);
    return;
  }
  if (s1[i] == s2[i]) {
    d(i + 1, k, s1, s2, n, r);
    return;
  }
  if (k + needSwap(i + 1, s1, s2, n) >= *r) return;
  for (int j = i + 1; j < n; j++) {
    if (s1[j] == s2[i]) {
      swap(s1, i, j);
      d(i + 1, k + 1, s1, s2, n, r);
      swap(s1, i, j);
    }
  }
}
int kSimilarity(char * s1, char * s2){
  int r = INT_MAX;
  d(0, 0, s1, s2, strlen(s1), &r);
  return r;
}

class Solution {
public:
  int r = INT_MAX;
  int n;
  char* c1;
  string s2;
  int kSimilarity(string s1, string s2) {
    n = s1.length();
    c1 = new char[n + 1];
    strcpy(c1, s1.c_str());
    this->s2 = s2;
    d(0, 0);
    return r;
  }
  void d(int i, int k) {
    if (i == n) {
      r = min(r, k);
      return;
    }
    if (c1[i] == s2[i]) {
      d(i + 1, k);
      return;
    }
    if (k + needSwap(i + 1) >= r) return;
    for (int j = i + 1; j < n; j++) {
      if (c1[j] == s2[i]) {
        swap(c1[i], c1[j]);
        d(i + 1, k + 1);
        swap(c1[i], c1[j]);
      }
    } 
  }
  int needSwap(int start) {
    int need = 0;
    for (int i = start; i < n; i++) if (c1[i] != s2[i]) need++;
    return need >> 1;
  }
};

class Solution:
  def kSimilarity(self, s1: str, s2: str) -> int:
    n, l1, r = len(s1), list(s1), sys.maxsize
    def swap(a: int, b: int):
      nonlocal l1
      l1[a], l1[b] = l1[b], l1[a]
    def needSwap(start: int) -> int:
      nonlocal n, l1, s2
      return sum([1 if l1[i] != s2[i] else 0 for i in range(start, n)]) >> 1
    def d(i: int, k: int):
      nonlocal n, r
      if i == n:
        r = min(r, k)
        return
      if l1[i] == s2[i]: return d(i + 1, k)
      if k + needSwap(i + 1) >= r: return
      for j in range(i + 1, n):
        if l1[j] == s2[i]:
          swap(i, j)
          d(i + 1, k + 1)
          swap(i, j)
    d(0, 0)
    return r