String.startsWith(String)
String.startsWith(String, int index)
图里的深度优先搜索
17 Letter Combinations of a Phone Number
291 Word Pattern II
127 Word Ladder
126 Word Ladder II
79 Word Search
212 Word Search II
基于图的深度优先搜索
17. Letter Combinations of a Phone Number
时间复杂度：3digit.length()~4digit.length()
class Solution {
String[][] map = { {},{}, {"a","b","c"}, {"d","e","f"}, {"g","h","i"}, {"j","k","l"}, {"m","n","o"},{"p","q","r","s"},{"t","u","v"},{"w","x","y", "z"}};
public List<String> letterCombinations(String digits) {
List<String> results = new ArrayList<>();
if(digits==null || digits.length()==0)
return results;
helper(digits, 0, results, "");
return results;
}
private void helper(String digits, int index, List<String> results, String result){
if(result.length()==digits.length()){
results.add(result);
return;
}
int num = Integer.parseInt(digits.charAt(index)+"");
for(int j=0; j<map[num].length; j++){
helper(digits, index+1, results, result + map[num][j]);
}
}
}
如果有一个词典(Dictionary)，要求组成的单词都是词典里的，如何优化?
用 Trie 或者 Hash 都可以:
用Hash：可以先遍历词典 把前缀和单词存入hashmap，然后搜索的时候判断是不是在map里就可以了
291. Word Pattern II
Input: pattern = "abab", str = "redblueredblue"
Output: true
字符和单词一一对应
Assume string length is n, and pattern string length is m.
Time complexity: the problem is more like slicing the string into m pieces. How many slicing ways?组合数Cnm. For each slice, it takes O(n) to validate. So the total complexity is O(n * C(nm))
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Set<String> set = new HashSet<>();
Map<Character, String> map = new HashMap<>();
return helper(pattern, str, 0, 0, map, set);
}
private boolean helper(String pattern, String str, int indexp, int indexs, Map<Character, String> map, Set<String> set){
if(indexp==pattern.length())
return indexs==str.length();
if(indexs==str.length())
return indexp==pattern.length();
char c = pattern.charAt(indexp);
if(map.containsKey(c)){
String matchString = map.get(c);
if(str.startsWith(matchString, indexs))
return helper(pattern, str, indexp+1, indexs+matchString.length(), map, set);
return false;
}else{
for(int i=indexs; i<str.length(); i++){
String checkString = str.substring(indexs, i+1);
if(set.contains(checkString))
continue;
map.put(c, checkString);
set.add(checkString);
if(helper(pattern, str, indexp+1, indexs+checkString.length() ,map, set))
return true;
map.remove(c);
set.remove(checkString);
}
}
return false;
}
}
127. Word Ladder
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>();
for(String word : wordList){
set.add(word);
}
// set.add(endWord);
return bfs(beginWord, endWord, set);
}
private int bfs(String beginWord, String endWord, Set<String> set){
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int result = 0;
Set<String> visited = new HashSet<>();
while(!queue.isEmpty()){
int size = queue.size();
result = result+1;
for(int i=0; i<size; i++){
String current = queue.poll();
if(current.equals(endWord)){
return result;
}
// visited.add(current);
for(String nextWord: nextWords(current, set)){
if(!visited.contains(nextWord)){
queue.offer(nextWord);
visited.add(nextWord);
}
}
}
}
return 0;
}
private List<String> nextWords(String word, Set<String> set){
//这个操作的时间复杂度是 O(26*wordlength^2)
List<String> result = new ArrayList<>();
for(int i=0; i<word.length(); i++){
for(char j='a'; j<='z'; j++){
if(word.charAt(i)==j)
continue;
String newWord = newword(word, i, j);
if(set.contains(newWord))
result.add(newWord);
}
}
return result;
}
private String newword(String word, int index, char c){
char[] chars = word.toCharArray();
chars[index] = c;
return new String(chars);
}
}
126. Word Ladder II
一定要在得到下一层结果时候就处理 不要在每次出队的时候再处理 这样能减少重复入队
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> results = new ArrayList<>();
Set<String> dict = new HashSet<>();
for(String word: wordList){
dict.add(word);
}
dict.add(beginWord);
Map<String, Integer> distances = new HashMap<>();
bfs(endWord, dict, distances);
List<String> temp = new ArrayList<String>();
temp.add(beginWord);
dfs(beginWord, endWord, dict, distances, results, temp);
return results;
}
private void dfs(String beginWord, String endWord,
Set<String> dict, Map<String, Integer> distances,
List<List<String>> results, List<String> temp){
//这里不用判断是否访问过 只用向距离终点更近的点走就可以
if(beginWord.equals(endWord)){
results.add(new ArrayList<String>(temp));
return;
}
for(String next: nextWords(beginWord, dict)){
if(distances.get(beginWord)>distances.get(next)){
temp.add(next);
dfs(next, endWord, dict, distances, results, temp);
temp.remove(temp.size()-1);
}
}
}
private void bfs(String endWord, Set<String> dict, Map<String, Integer> distances){
//map一方面存距离 另一方面存是否访问过
Queue<String> queue = new LinkedList<>();
queue.offer(endWord);
int dis = 0;
distances.put(endWord, 0);
while(!queue.isEmpty()){
int size = queue.size();
dis = dis+1;
for(int i=0; i<size; i++){
String current = queue.poll();
for(String nextWord: nextWords(current, dict)){
if(!distances.containsKey(nextWord)){
distances.put(nextWord, dis);
queue.offer(nextWord);
}
}
}
}
}
private List<String> nextWords(String word,Set<String> set){
List<String> result = new ArrayList<>();
for(int i=0; i<word.length(); i++){
for(char j='a'; j<='z'; j++){
if(word.charAt(i)==j)
continue;
String newWord = newword(word, i, j);
if(set.contains(newWord)){
result.add(newWord);
}
}
}
return result;
}
private String newword(String word, int index, char c){
char[] chars = word.toCharArray();
chars[index] = c;
return new String(chars);
}
}
79. Word Search
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
if(find(board, i, j, word, visited, 0))
return true;
}
}
return false;
}
private boolean isValid(char[][] board,int x, int y, boolean[][] visited){
if(x>=0 && x<board.length && y>=0 && y<board[0].length && visited[x][y]==false)
return true;
return false;
}
private boolean find(char[][] board,int x, int y, String word, boolean[][] visited, int index){
int[] dirx = {1,-1,0,0};
int[] diry = {0,0,1,-1};
if(index == word.length())
return true;
if(!isValid(board, x, y, visited))
return false;
if(word.charAt(index)!=board[x][y])
return false;
visited[x][y] = true;
for(int i=0; i<4; i++){
if(find(board, x+dirx[i], y+diry[i], word, visited, index+1))
return true;
}
visited[x][y] = false;
return false;
}
}
212. Word Search II
- 用hashmap
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Set<String> prefixs = new HashSet<>();
Set<String> wordSet = new HashSet<>();
for(int j=0; j<words.length; j++){
String word = words[j];
wordSet.add(word);
for(int i=0; i<word.length(); i++){
String prefix = word.substring(0, i+1);
prefixs.add(prefix);
}
}
boolean[][] visited = new boolean[board.length][board[0].length];
Set<String> results = new HashSet<>();
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
visited[i][j] = true;
helper(board, visited, i, j, prefixs, wordSet, results, String.valueOf(board[i][j]));
visited[i][j] = false;
}
}
return new ArrayList<String>(results);
}
private void helper(char[][] board, boolean[][] visited, int x, int y, Set<String> prefixs, Set<String> wordSet, Set<String> results, String temp){
if(wordSet.contains(temp)){
results.add(temp);
}
if(!prefixs.contains(temp))
return;
int[] dirx = {1,-1,0,0};
int[] diry = {0,0,1,-1};
for(int i=0; i<4; i++){
if(isValid(board, x+dirx[i], y+diry[i], visited)){
visited[x+dirx[i]][y+diry[i]] = true;
helper(board, visited, x+dirx[i], y+diry[i], prefixs, wordSet, results, temp+board[x+dirx[i]][y+diry[i]]);
visited[x+dirx[i]][y+diry[i]] = false;
}
}
}
private boolean isValid(char[][] board,int x, int y, boolean[][] visited){
if(x>=0 && x<board.length && y>=0 && y<board[0].length && visited[x][y]==false)
return true;
return false;
}
}
- 用trie
class Solution {
static class TrieNode{
TrieNode[] children;
TrieNode(){
children = new TrieNode[26];
}
}
static TrieNode root;
private static void build(String[] words){
for(String word: words){
builderHelper(word);
}
}
private static void builderHelper(String word){
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null)
current.children[index] = new TrieNode();
current = current.children[index];
}
}
private static boolean startWith(String word){
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current==null || current.children[index]==null)
return false;
current = current.children[index];
}
return true;
}
public static List<String> findWords(char[][] board, String[] words) {
Set<String> results = new HashSet<>();
root = new TrieNode();
build(words);
Set<String> set = new HashSet<>();
for(String s: words){
set.add(s);
}
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
StringBuilder sb = new StringBuilder();
sb.append(board[i][j]);
visited[i][j] = true;
helper(i, j, board, set, results, sb, visited);
visited[i][j] = false;
}
}
List<String> solutions = new ArrayList<>();
for(String s: results){
solutions.add(s);
}
return solutions;
}
private static void helper(int row, int col, char[][] board, Set<String> set, Set<String> results, StringBuilder sb, boolean[][] visited){
if(set.contains(sb.toString()))
results.add(sb.toString());
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, -1, 1};
for(int i=0; i<4; i++){
int x = row + dirx[i];
int y = col + diry[i];
if(!valid(x, y, visited)){
continue;
}
sb.append(board[x][y]);
if(!startWith(sb.toString())){
sb.deleteCharAt(sb.length()-1);
continue;
}
visited[x][y] = true;
helper(x, y, board, set, results, sb, visited);
sb.deleteCharAt(sb.length()-1);
visited[x][y] = false;
}
}
private static boolean valid(int x, int y, boolean[][] visited){
return x>=0 && x<visited.length && y>=0 && y<visited[0].length && !visited[x][y];
}
}
网友评论