做seo推广手机网站,新闻最近的新闻,项目网课商城,wordpress app一键生成题目链接 Leetcode.1247 交换字符使得字符串相同 Rating #xff1a; 1597 题目描述
有两个长度相同的字符串 s1和 s2#xff0c;且它们其中 只含有 字符 x和 y#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时…题目链接 Leetcode.1247 交换字符使得字符串相同 Rating 1597 题目描述
有两个长度相同的字符串 s1和 s2且它们其中 只含有 字符 x和 y你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间绝对不能发生在同一个字符串内部。也就是说我们可以交换 s1[i]和 s2[j]但不能交换 s1[i]和 s1[j]。
最后请你返回使 s1和 s2相同的最小交换次数如果没有方法能够使得这两个字符串相同则返回 -1。
示例 1 输入s1 “xx”, s2 “yy” 输出1 解释 交换 s1[0] 和 s2[1]得到 s1 “yx”s2 “yx”。 示例 2 输入s1 “xy”, s2 “yx” 输出2 解释 交换 s1[0] 和 s2[0]得到 s1 “yy”s2 “xx” 。 交换 s1[0] 和 s2[1]得到 s1 “xy”s2 “xy” 。 注意你不能交换 s1[0] 和 s1[1] 使得 s1 变成 “yx”因为我们只能交换属于两个不同字符串的字符。 示例 3 输入s1 “xx”, s2 “xy” 输出-1 示例 4 输入s1 “xxyyxyxyxx”, s2 “xyyxyxxxyx” 输出4 提示
1s1.length,s2.length10001 s1.length, s2.length 10001s1.length,s2.length1000s1, s2只包含 x或 y。
分析
我们只需要讨论 s1[i] ! s2[i]即不匹配的情况。
我们用 k表示不能匹配的数量。
我们发现当 k是奇数时无论怎么也不能让 s1 s2。 只有当 k是偶数时才能通过交换让 s1 s2。
示例已经给出了 交换 的两种形式。 所以为了让操作次数最少我们应该尽量用第一种交换方式。
当 x和y的数量都是偶数时 当 x和y的数量都是奇数时 时间复杂度O(n)O(n)O(n)
C代码
class Solution {
public:int minimumSwap(string s1, string s2) {int n s1.size();unordered_mapchar,int cnt;int k 0;for(int i 0;i n;i){if(s1[i] ! s2[i]){k;cnt[s1[i]];}}if(k % 2) return -1;return k / 2 cnt[x] % 2;}
};Java代码
class Solution {public int minimumSwap(String s1, String s2) {int n s1.length();int[] cnt new int[2];int k 0;for(int i 0;i n;i){if(s1.charAt(i) ! s2.charAt(i)){k;//x - x 0 , y - x 1cnt[s1.charAt(i) - x];}}if(k % 2 1) return -1;return k/2 cnt[0] % 2;}
}
