BFS & DFS

Word Ladder

题目

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

给定起始单词和结束单词，利用wordlist中的单词爬梯子，每次只允许改变一个字母，返回能够到达结束词的最短路径长度

分析

一开始用了回溯，相当于暴力了所有可能，超时了，看了解答，这道题应该用广度优先搜索（BFS）：

需要用到队列Queue

因为要求最短路径，如果我们用深度优先搜索的话必须遍历所有的路径才能确定哪个是最短的，而用广度优先搜索的话，一旦搜到目标就可以提前终止了，而且根据广度优先的性质，我们肯定是先通过较短的路径搜到目标。另外，为了避免产生环路和重复计算，我们找到一个存在于字典的新的词时，就要把它从字典中移去。这么做是因为根据广度优先，我们第一次发现词A的路径一定是从初始词到词A最短的路径，对于其他可能再经过词A的路径，我们都没有必要再计算了。

代码

boolean[] isUsed;

//判断两个单词是否只相差一个字母
public boolean isValid(String word1, String word2){
  if(word1.length() != word2.length()){
    return false;
  }
  int diffSum = 0;
  for(int i = 0; i < word1.length();i++){
    if(word1.charAt(i) != word2.charAt(i)){
      diffSum++;
      if(diffSum > 1){
        return false;
      }
    }
  }
  return true;
}

public int solve(String beginWord, String endWord, List<String> wordList){
  Queue<String> queue = new LinkedList<>();
  queue.add(beginWord);
  int step = 2;//记录层数
  while(!queue.isEmpty()){
    int queueSize = queue.size();//当前queue长度
    for(int i = 0 ; i < queueSize;i++){//遍历queue中元素，将其后续节点入队列
      String temp  = queue.peek();
      for(int j = 0 ; j <wordList.size();j++){
        //如果该词与队列顶端元素只相差一个字母，入队列，标记为使用过
        if(!isUsed[j] && isValid(temp,wordList.get(j))){
          if(wordList.get(j).equals(endWord)){//一旦找到了endword结束搜索，返回当前层数
            return step;
          }
          queue.add(wordList.get(j));
          isUsed[j] = true;
        }
      }
      queue.poll();
    }
    step++;//层数+1
  }
  return 0;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
  isUsed = new boolean[wordList.size()];
  return solve(beginWord,endWord,wordList);
}

Remove Invalid Parentheses

emove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

> "()())()" -> ["()()()", "(())()"]
> "(a)())()" -> ["(a)()()", "(a())()"]
> ")(" -> [""]
>

思路：

BFS:set+queue

用set记录出现过的字符串，将字符串放入queue，一次删除一个字符，如果在set中没有出现，放入queue。

每次弹出一个字符串判断是否为合法字符串，如果合法加入结果集

由于只能返回去掉字符最少的字符串，所以采用按层遍历的方式，一旦某一层出现了合法字符串，本层遍历结束之后就返回结果，不再验证后面的字符串

DFS:

论坛上的高票解法，非常巧妙

核心思想就是记录当前出现过的左右括号数目，当右括号多于左括号时，说明从此位置向前可以删掉一个右括号，用dfs依次遍历删除此位置之前的每一个右括号，这里需要注意的有几点：

1. 对于相邻的右括号，删除哪一个都一样，所以只删除第一个就好
2. 需要记录上一轮删除右括号的位置，下一轮dfs的时候不需要再删除在此之前的右括号
3. dfs到字符串末尾，说明字符串中的右括号不比左括号多了，但还需要保证左括号不比右括号多，所以需要将字符串翻转，再来一遍，最后满足条件了才可以放入结果集

很难写出来的，看了答案写的，还没吃透，需要复习！！！

代码：

bfs:

public boolean isValid(String s){
    int leftNum = 0;
    int rightNum = 0;
    for(int i = 0;i < s.length();i++){
        if(s.charAt(i) == '('){
            leftNum++;
        }
        if(s.charAt(i) == ')'){
            rightNum++;
            if(rightNum > leftNum){
                return false;
            }
        }
    }
    return leftNum == rightNum;
}

public List<String> removeInvalidParentheses(String s) {
    List<String> res = new ArrayList<>();
    Set<String> set = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
    if(s.isEmpty() || isValid(s)){
        res.add(s);
        return res;
    }
    queue.add(s);
    set.add(s);
    while(!queue.isEmpty()){
        int size = queue.size();
        while(size > 0){
            String temp = queue.poll();
            if(isValid(temp)){
                res.add(temp);
            }
            for(int i = 0; i < temp.length();i++){
                if(temp.charAt(i) != '(' && temp.charAt(i) != ')'){continue;}
                String t = temp.substring(0,i)+temp.substring(i+1,temp.length());
                if(!set.contains(t)){
                    queue.add(t);
                    set.add(t);
                }
            }
            size--;
        }
        if(res.size() > 0){
            return res;
        }
    }
    return res;
}

dfs:

import java.util.ArrayList;
import java.util.List;

public class RemoveInvalidParenthess {
    //idx_i: idx_i以前左右括号数量相等    ddx_j:从idx_j开始）没有被删除了
    public void dfs(String s,int idx_i,int idx_j,List<String> res,char[] ch){
        int leftNum = 0;
        int rightNum = 0;
        for(int i = idx_i;i < s.length();i++){
            if(s.charAt(i) == ch[0]){
                leftNum++;
            }
            if(s.charAt(i) == ch[1]){
                rightNum++;
                //如果右括号比左括号多了
            }
            if(rightNum <= leftNum){
                continue;
            }
            for(int j = idx_j;j <= i;j++){
                if(s.charAt(j) == ch[1] && (s.charAt(j-1) != ch[1] || j == idx_j)){
                    dfs(s.substring(0,j)+s.substring(j+1,s.length()),i,j,res,ch);
                }
            }
            return;
        }

        String reversed = new StringBuilder(s).reverse().toString();
        if(ch[0] == ')'){
            System.out.println(reversed);
            res.add(reversed);
        }
        else{
            dfs(reversed,0,0,res,new char[]{')','('});
        }

    }

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        dfs(s,0, 0, res, new char[]{'(', ')'});
        return res;
    }

    public static void main(String[] args){
        RemoveInvalidParenthess test = new RemoveInvalidParenthess();
        String s = "()())()";
        List<String> res = test.removeInvalidParentheses(s);
        System.out.println(res);
    }
}