交換字符使得字符串相同

題目描述

有兩個(gè)長度相同的字符串 s1 和 s2，且它們其中 只含有 字符 “x” 和 “y”，你需要通過「交換字符」的方式使這兩個(gè)字符串相同。

每次「交換字符」的時(shí)候，你都可以在兩個(gè)字符串中各選一個(gè)字符進(jìn)行交換。

交換只能發(fā)生在兩個(gè)不同的字符串之間，絕對(duì)不能發(fā)生在同一個(gè)字符串內(nèi)部。也就是說，我們可以交換 s1[i] 和 s2[j]，但不能交換 s1[i] 和 s1[j]。

最后，請(qǐng)你返回使 s1 和 s2 相同的最小交換次數(shù)，如果沒有方法能夠使得這兩個(gè)字符串相同，則返回 -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”，因?yàn)槲覀冎荒芙粨Q屬于兩個(gè)不同字符串的字符。

-1

4

提示

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

思路

先給x,y計(jì)數(shù)，如果x的數(shù)量或者y的數(shù)量不能整除2，那么可直接返回-1。
然后后面的結(jié)論就是把玩數(shù)據(jù)而推出來的結(jié)論，因?yàn)橐箂1[i]與s2[i]相等，就不需要改變進(jìn)行轉(zhuǎn)變就會(huì)相等，那么就只有s1[i] = x 且 s2[i] = y（后面簡稱為xy） || s1[i] = y 且 s2[i] = x（后面簡稱為yx）的情況。又通過把玩數(shù)據(jù)可知xy與xy消除只需要一次交換，yx與yx同理，而xy與yx消除需要兩次交換。
貪心的想，能使相同的兩種類型交換就盡可能的兩種相同類型進(jìn)行交換。

代碼實(shí)現(xiàn)

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

題目描述

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)單詞（字符串）列表 words， 返回所有二維網(wǎng)格上的單詞 。

單詞必須按照字母順序，通過 相鄰的單元格 內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。

樣例

樣例輸入

board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l(fā)”,“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] 是一個(gè)小寫英文字母
• $1<=words.length<=3?10^4$
• 1 <= words[i].length <= 10
• words[i] 由小寫英文字母組成
• words 中的所有字符串互不相同

思路

矩陣范圍很小，可直接上暴力回溯，能過。但現(xiàn)在還是學(xué)習(xí)更優(yōu)的加法才好。因?yàn)槭亲址臋z索，可使用字典樹進(jìn)行優(yōu)化。

代碼實(shí)現(xiàn)

回溯

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;}}
}

字典樹優(yōu)化

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;}}}
}