LeetCode(97) -- 127, 129

P127. Word Ladder (Medium)

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.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Solution

an undirected and unweighted graph, shortest path, so BFS. Regular expression

Approach 1:

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int length = beginWord.length();
        Map<String, List<String>> allComboDict = new HashMap<>();
        wordList.forEach(
            word -> {
                for (int i = 0; i < length; i++) {
                    String newWord = word.substring(0, i) + '*' + word.substring(i + 1, length);
                    List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                    transformations.add(word);
                    allComboDict.put(newWord, transformations);
                }
            }
        );
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(beginWord, 1));
        Map<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);
        while (!queue.isEmpty()) {
            Pair<String, Integer> node = queue.remove();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < length; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, length);
                for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                    if (adjacentWord.equals(endWord)) {
                        return level + 1;
                    }
                    if (!visited.containsKey(adjacentWord)) {
                        visited.put(adjacentWord, true);
                        queue.add(new Pair<>(adjacentWord, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

Approach 2: Bidirectional Breadth First Search

class Solution {
    private int L;
    private Map<String, List<String>> allComboDict = new HashMap<>();

    private int visitWordNode(Queue<Pair<String, Integer>> Q, Map<String, Integer> visited, Map<String, Integer> othersVisited) {
        Pair<String, Integer> node = Q.remove();
        String word = node.getKey();
        int level = node.getValue();
        for (int i = 0; i < L; i++) {
            String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
            for (String adjacentWord : this.allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                if (othersVisited.containsKey(adjacentWord)) {
                    return level + othersVisited.get(adjacentWord);
                }
                if (!visited.containsKey(adjacentWord)) {
                    visited.put(adjacentWord, level + 1);
                    Q.add(new Pair(adjacentWord, level + 1));
                }
            }
        }
        return -1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        this.L = beginWord.length();
        wordList.forEach(
            word -> {
                for (int i = 0; i < L; i++) {
                    String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                    List<String> transformations = this.allComboDict.getOrDefault(newWord, new ArrayList<>());
                    transformations.add(word);
                    this.allComboDict.put(newWord, transformations);
                }
            }
        );
        Queue<Pair<String, Integer>> Q_begin = new LinkedList<>();
        Queue<Pair<String, Integer>> Q_end = new LinkedList<>();
        Q_begin.add(new Pair(beginWord, 1));
        Q_end.add(new Pair(endWord, 1));
        Map<String, Integer> visitedBegin = new HashMap<>();
        Map<String, Integer> visitedEnd = new HashMap<>();
        visitedBegin.put(beginWord, 1);
        visitedEnd.put(endWord, 1);
        while (!Q_begin.isEmpty() && !Q_end.isEmpty()) {
            int ans = visitWordNode(Q_begin, visitedBegin, visitedEnd);
            if (ans > -1) {
                return ans;
            }
            ans = visitWordNode(Q_end, visitedEnd, visitedBegin);
            if (ans > -1) {
                return ans;
            }
        }
        return 0;
    }


}

The Best Solution

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordDict = new HashSet(wordList);
		if (!wordDict.contains(endWord)) {
			return 0;
		}
		Set<String> begin = new HashSet();
		Set<String> end = new HashSet();
		begin.add(beginWord);
		end.add(endWord);
		return helper(wordDict, begin, end, 1);
    }
	int helper(Set<String> wordDict, Set<String> begin, Set<String> end, int level) {
		if (begin.isEmpty() || end.isEmpty()) {
			return 0;
		}
		if (begin.size() > end.size()) {
			return helper(wordDict, end, begin, level);
		}
		wordDict.removeAll(begin);
		Set<String> next = new HashSet();
		for (String word : begin) {
			char[] chars = word.toCharArray();
			for (int i = 0; i < chars.length; i++) {
				char old = chars[i];
				for (char c = 'a'; c <= 'z'; c++) {
					chars[i] = c;
					String newWord = new String(chars);
					if (!wordDict.contains(newWord)) {
						continue;
					}
					if (end.contains(newWord)) {
						return level + 1;
					}
					next.add(newWord);
				}
				chars[i] = old;
			}
		}
		return helper(wordDict, next, end, level + 1);
	}
}

都放在set里，然后把每个字母挨个换，换完后如果在原始的字典里有，就把它看成下一次的起始点，放到next里。凡是做过起始点的，都从原始的字典里移除。

P129. Sum Root to Leaf Numbers (Medium)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

My Solution

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null){
            return sum;
        }
        dfs(root, 0);
        return sum;
    }
    
    private void dfs(TreeNode node, int current) {
        current = current * 10 + node.val;
        if (node.left == null && node.right == null) {
            sum += current;
            return;
        }
        if (node.left != null) {
            dfs(node.left, current);
        }
        if (node.right != null) {
            dfs(node.right, current);
        }
    }
}

100% 这个题非常简单，就用自己的代码没有问题。