交换字符使得字符串相同

题目描述

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

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

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

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

样例

样例输入

s1 = “xx”, s2 = “yy”
s1 = “xy”, s2 = “yx”
s1 = “xx”, s2 = “xy”
s1 = “xxyyxyxyxx”, s2 = “xyyxyxxxyx”

样例输出

1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = “yx”，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”，因为我们只能交换属于两个不同字符串的字符。

-1

4

提示

• 1 <= s1.length, s2.length <= 1000
• s1, s2 只包含 ‘x’ 或 ‘y’。

思路

先给x,y计数，如果x的数量或者y的数量不能整除2，那么可直接返回-1。
然后后面的结论就是把玩数据而推出来的结论，因为要使s1[i]与s2[i]相等，就不需要改变进行转变就会相等，那么就只有s1[i] = x 且 s2[i] = y（后面简称为xy） || s1[i] = y 且 s2[i] = x（后面简称为yx）的情况。又通过把玩数据可知xy与xy消除只需要一次交换，yx与yx同理，而xy与yx消除需要两次交换。
贪心的想，能使相同的两种类型交换就尽可能的两种相同类型进行交换。

代码实现

class Solution {public int minimumSwap(String s1, String s2) {int n = s1.length();int c1 = 0, c2 = 0;int top = 0, bottom = 0;for(int i = 0; i < n; i++){c1 += (s1.charAt(i) == 'x' ? 1 : 0) + (s2.charAt(i) == 'x' ? 1: 0);c2 += (s1.charAt(i) == 'y' ? 1 : 0) + (s2.charAt(i) == 'y' ? 1: 0);if(s1.charAt(i) != s2.charAt(i)){if(s1.charAt(i) == 'x') top++;else bottom++;}}if(c1 % 2 != 0 || c2 % 2 != 0) return -1;int ans = 0;ans += top / 2;ans += bottom / 2;top %= 2;bottom %= 2;if(top == 1 && bottom == 1) ans += 2;return ans;}
}

单词搜索 II

题目描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

样例

样例输入

board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]

样例输出

[“eat”,“oath”]
[]

提示

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• $1<=words.length<=3\ast 10^4$
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

思路

矩阵范围很小，可直接上暴力回溯，能过。但现在还是学习更优的加法才好。因为是字符串的检索，可使用字典树进行优化。

代码实现

回溯

class Solution {int m, n;HashSet<String> set = new HashSet<>();List<String> ans = new ArrayList<>();char[][] board;boolean[][] vis = new boolean[15][15];int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};public List<String> findWords(char[][] board, String[] words) {m = board.length;n = board[0].length;this.board = board;for(String w : words) set.add(w);StringBuilder sb = new StringBuilder();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){vis[i][j] = true;sb.append(board[i][j]);dfs(i, j, sb);sb.deleteCharAt(sb.length()-1);vis[i][j] = false;}}return ans;}private void dfs(int i, int j, StringBuilder sb){if(sb.length() > 10) return ;if(set.contains(sb.toString())){ans.add(sb.toString());set.remove(sb.toString());}for(var d : dir){int x = d[0] + i, y = d[1] + j;if(x < 0 || x == m || y < 0 || y == n || vis[x][y]) continue;vis[x][y] = true;sb.append(board[x][y]);dfs(x, y, sb);sb.deleteCharAt(sb.length() - 1);vis[x][y] = false;}}
}

字典树优化

class Solution {class TreeNode{String s;TreeNode[] next = new TreeNode[26]; }void insert(String s){TreeNode p = root;for(int i = 0; i < s.length(); i++){int u = s.charAt(i) - 'a';if(p.next[u] == null) p.next[u] = new TreeNode();p = p.next[u]; }p.s = s;}int m, n;HashSet<String> set = new HashSet<>();TreeNode root = new TreeNode();char[][] board;int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};boolean[][] vis = new boolean[15][15];public List<String> findWords(char[][] board, String[] words) {m = board.length;n = board[0].length;this.board = board;for(String w : words) insert(w);StringBuilder sb = new StringBuilder();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int u = board[i][j] - 'a';if(root.next[u] != null){vis[i][j] =true;dfs(i, j, root.next[u]);vis[i][j] = false;}}}List<String> ans = new ArrayList<>();for(var s : set) ans.add(s);return ans;}private void dfs(int i, int j, TreeNode node){if(node.s != null) set.add(node.s);for(var d : dir){int x = d[0] + i, y = d[1] + j;if(x < 0 || x == m || y < 0 || y == n || vis[x][y]) continue;int u = board[x][y] - 'a';if(node.next[u] != null){vis[x][y] = true;dfs(x, y, node.next[u]);vis[x][y] = false;}}}
}