字符串公共元素问题

Question 1

给定两个字符串，找出他们的相同元素。

注：可以把字符串换成数组。

Answer 1

双循环遍历法

算法思想：

1. 遍历字符串A；
2. 对A的每个元素，遍历字符串B；
3. 遇到相同元素就加入结果数组。

排序遍历法

算法思想：

1. 对字符串A与B按字母顺序排序；
2. 设双指针分别指向字符串A的首位和字符串B的首位；
3. 比较两个指针指向的值的字母位序大小：
   1. 若A大于B，则B指针后移；
   2. 若A小于B，则A指针后移；
   3. 若A等于B，则加入结果数组，双指针同时后移。

哈希查找法

算法思想：

1. 将字符串A、B的所有元素分别加入哈希表a和b；
2. 对哈希表a的每个元素，在哈希表b中查找；
3. 若查找到，则加入结果数组，直到哈希表a的元素遍历结束为止。

Question 2

有两个长度相同的字符串s1和s2，且它们其中只含有字符”x” 和”y”，你需要通过“交换字符“的方式使这两个字符串相同。

每次“交换字符“的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换s1[i] 和s2[j]，但不能交换s1[i]和s1[j]。

最后，请你返回使s1和s2相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回-1。

Answer 2

由于字符串里只有两种字母 x 和 y，因此统计位置的匹配情况，一共只有 4 种可能，即 x - x，x - y，y - x，y - y。

其中 x - x 和 y - y 都是已经能匹配的情况，不需要额外操作。剩余的是：

1. x - y，假设有 a 对。
2. y - x，假设有 b 对。

对于两对 x - y 或者 y - x，我们都是可以通过一次交换使得他们变为 x - x，y - y 的；

对于一对 x - y 或一对 y- x 的情况，我们需要通过“两次“操作使他们变为 x - x，y - y；

综上，优先使两对一样的进行交换操作；操作结束后，剩余的情况有以下几种：

1. a,b 都是偶数，那么最后无剩余，不需要额外操作。
2. a,b 一奇一偶，最后只会剩下一对不匹配字符，无解返回-1。
3. a,b 都是奇数，那么最后会剩下一对 x - y 和一对 y - x，需要额外 2 次操作。

我们的主要计算代价是开头统计的时候会遍历字符串，所以时间复杂度为 O(n)。

int minimumSwap(string str1,string str2)
{
    int count = 0; //交换次数
    int xy = 0, yx = 0 ,len = str1.size();
    for(int i=0; i<len; i++) 
    {
        if(str1[i] != str2[i])
            if(str1[i] == 'x')
                xy++;
            else
                yx++;
    }
    //两个都是偶数不需要额外操作
    if((xy+yx) % 2 == 1)//两者一奇一偶
        return -1;
    count = xy/2 +yx/2;
    if(xy%2 == 1 && yx%2 == 1)//两个都是奇数
        count += 2;
    return count;
}