leetcode 854 相似度为K的字符串（dfs)

题目描述：
如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。

给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。

思路：
A:a b c
pos i
B:b c a

总的方向是从左到右依次交换，直到一样
首先如果A[pos]!=B[pos]
然后如果A[i]==B[pos]，那么则交换，并且要保证A[i]!=B[i]，一样的就不交换了

代码如下：

class Solution {
public:
    int res,n;
    int kSimilarity(string A, string B) {
        n=A.size();
        res=n+1;
        dfs(A,B,0,0);
        return res;
    }
    void dfs(string& A,string& B,int pos,int step){
        if(step>=res){
            return;
        }
        if(pos==n){
            res=min(res,step);
            return;
        }
        if(A[pos]==B[pos]){
            dfs(A,B,pos+1,step);
        }
        else{
            for(int i=pos+1;i<n;i++){
                if(A[i]==B[pos]&&A[i]!=B[i]){
                    swap(A[i],A[pos]);
                    dfs(A,B,pos+1,step+1);
                    swap(A[i],A[pos]);
                }
            }
        }
        
    }
};