[leetcode题解]859. Buddy Strings

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

 

Example 1:

Input: A = "ab", B = "ba" Output: true 

Example 2:

Input: A = "ab", B = "ab" Output: false 

Example 3:

Input: A = "aa", B = "aa" Output: true 

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb" Output: true 

Example 5:

Input: A = "", B = "aa" Output: false 

 

Note:

  1. 0 <= A.length <= 20000
  2. 0 <= B.length <= 20000
  3. A and B consist only of lowercase letters.                                          

此题思路比较明确,如果两个字符串不等长,肯定不满足条件,在等长的情况下,如果两个字符串相同,则只要包含相同字母则能满足条件,如果两个字符串不相同,要想满足条件,必须保证两者有且仅有两个字符不相同,并且这两个字符的书序相反即可。

c代码如下:

bool hasSame(char *str, int len) {
    int i = 0;
    int j = 0;
    
    for (i = 0; i < len; i++) {
        for (j = i + 1; j < len; j++) {
            if (str[i] == str[j])
                return true;
        }
    }
    return false;
}

bool buddyStrings(char* A, char* B) {
    int lena = 0;
    int lenb = 0;
    int i = 0;
    int diff = 0;
    char sa[2] = {'\0'};
    char sb[2] = {'\0'};
    
    lena = strlen(A);
    lenb = strlen(B);
    
    if (lena != lenb)
        return false;
    
    if (strcmp(A, B) == 0 && hasSame(A, lena))
        return true;
    
    for (i = 0; i < lena; i++) {
        if (A[i] == B[i])
            continue;
        
        if (diff < 2) {
            sa[diff] = A[i];
            sb[diff] = B[i];
        }
        diff++;
        if (diff > 2)
            return false;
    }
    
    if (diff == 2 && sa[0] == sb[1] && sa[1] == sb[0])
        return true;
    
    return false;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]859. Buddy Strings

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/157.html

相关文章