Merge pull request #462 from TTWShell/feature/200-300-hard

TTWShell · web-flow · commit 5fc0b584f436 · 2020-03-18T10:42:32.000+08:00
Feature/200 300 hard
diff --git a/leetcode/README.md b/leetcode/README.md
@@ -185,7 +185,9 @@
 | 209 | [Minimum Size Subarray Sum](binary-search/minSubArrayLen.go) | [Medium][] |
 | 210 | [Course Schedule II](graph/findOrder.go) | [Medium][] |
 | 211 | [Add and Search Word - Data structure design](design/WordDictionary.go) | [Medium][] |
+| 212 | [Word Search II](trie/findWords.go) | [Hard][] |
 | 213 | [House Robber II](dynamic-programming/rob2.go) | [Medium][] |
+| 214 | [Shortest Palindrome](string/shortestPalindrome.go) | [Hard][] |
 | 215 | [Kth Largest Element in an Array](heap/findKthLargest.go) | [Medium][] |
 | 216 | [Combination Sum III](backtracking/combinationSum3.go) | [Medium][] |
 | 217 | [Contains Duplicate](hash-table/containsDuplicate.go) | [Easy][] |
diff --git a/leetcode/string/shortestPalindrome.go b/leetcode/string/shortestPalindrome.go
@@ -0,0 +1,42 @@
+/* https://leetcode.com/problems/shortest-palindrome/
+Given a string s, you are allowed to convert it to a palindrome by
+ adding characters in front of it. Find and return the shortest
+ palindrome you can find by performing this transformation.
+
+Example 1:
+
+	Input: "aacecaaa"
+	Output: "aaacecaaa"
+
+Example 2:
+
+	Input: "abcd"
+	Output: "dcbabcd"
+*/
+
+package lstring
+
+func shortestPalindrome(s string) string {
+	isPalindrome := func(start, end int) bool {
+		for i := start; i < start+(end-start)/2; i++ {
+			if s[i] != s[end-1-i] {
+				return false
+			}
+		}
+		return true
+	}
+
+	end := len(s)
+	for ; end >= 1; end-- {
+		if isPalindrome(0, end) {
+			break
+		}
+	}
+
+	tmp, idx := make([]byte, len(s)-end), 0
+	for i := len(s) - 1; i >= end; i-- {
+		tmp[idx] = s[i]
+		idx++
+	}
+	return string(tmp) + s
+}
diff --git a/leetcode/string/shortestPalindrome_test.go b/leetcode/string/shortestPalindrome_test.go
@@ -0,0 +1,15 @@
+package lstring
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func Test_shortestPalindrome(t *testing.T) {
+	assert := assert.New(t)
+
+	assert.Equal("abba", shortestPalindrome("abba"))
+	assert.Equal("aaacecaaa", shortestPalindrome("aacecaaa"))
+	assert.Equal("dcbabcd", shortestPalindrome("abcd"))
+}
diff --git a/leetcode/trie/findWords.go b/leetcode/trie/findWords.go
@@ -0,0 +1,99 @@
+/* https://leetcode.com/problems/word-search-ii/
+Given a 2D board and a list of words from the dictionary, find all words in the board.
+
+Each word must be constructed from letters of sequentially adjacent cell,
+where "adjacent" cells are those horizontally or vertically neighboring.
+The same letter cell may not be used more than once in a word.
+
+Example:
+
+	Input:
+	board = [
+	['o','a','a','n'],
+	['e','t','a','e'],
+	['i','h','k','r'],
+	['i','f','l','v']
+	]
+	words = ["oath","pea","eat","rain"]
+
+	Output: ["eat","oath"]
+
+Note:
+
+	All inputs are consist of lowercase letters a-z.
+	The values of words are distinct.
+*/
+
+package ltrie
+
+type ByteTrie struct {
+	IsRoot bool
+	Root   string
+	Next   map[byte]*ByteTrie
+}
+
+func ByteTrieConstructor(dict []string) ByteTrie {
+	trie := &ByteTrie{IsRoot: false, Next: map[byte]*ByteTrie{}}
+	for _, word := range dict {
+		var (
+			cur, end = trie, len(word)
+			tmp      *ByteTrie
+		)
+		for i := range word {
+			c := word[i]
+			if next, ok := cur.Next[c]; ok {
+				cur = next
+			} else {
+				tmp = &ByteTrie{IsRoot: false, Next: map[byte]*ByteTrie{}}
+				cur.Next[c] = tmp
+				cur = tmp
+			}
+		}
+		cur.Root = word[0:end]
+		cur.IsRoot = true
+	}
+	return *trie
+}
+
+func findWords(board [][]byte, words []string) []string {
+	if len(board) == 0 {
+		return []string{}
+	}
+
+	trie := ByteTrieConstructor(words)
+
+	m, n := len(board), len(board[0])
+	tmp := map[string]int{}
+	var path map[[2]int]bool
+
+	var search func(i, j int, trie *ByteTrie)
+	search = func(i, j int, trie *ByteTrie) {
+		char := board[i][j]
+		path[[2]int{i, j}] = true
+		if subTrie, ok := trie.Next[char]; ok {
+			if subTrie.IsRoot {
+				tmp[subTrie.Root]++
+			}
+			for _, point := range [][2]int{{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}} {
+				idxI, idxJ := point[0], point[1]
+				if 0 <= idxI && idxI < m && 0 <= idxJ && idxJ < n && !path[[2]int{idxI, idxJ}] {
+					search(idxI, idxJ, subTrie)
+				}
+			}
+		}
+		path[[2]int{i, j}] = false
+	}
+
+	for i := 0; i < m; i++ {
+		for j := 0; j < n; j++ {
+			path = map[[2]int]bool{}
+			search(i, j, &trie)
+		}
+	}
+
+	res := make([]string, 0, len(tmp))
+	for word := range tmp {
+		res = append(res, word)
+	}
+	return res
+}
diff --git a/leetcode/trie/findWords_test.go b/leetcode/trie/findWords_test.go
@@ -0,0 +1,61 @@
+package ltrie
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func Test_findWords(t *testing.T) {
+	assert := assert.New(t)
+
+	assert.Equal([]string{}, findWords([][]byte{}, []string{"cdba"}))
+
+	board := [][]byte{
+		{'o', 'a', 'a', 'n'},
+		{'e', 't', 'a', 'e'},
+		{'i', 'h', 'k', 'r'},
+		{'i', 'f', 'l', 'v'},
+	}
+	excepted := []string{"eat", "oath"}
+	result := findWords(board, []string{"oath", "pea", "eat", "rain"})
+	assert.Subset(excepted, result)
+	assert.Len(result, 2)
+
+	board = [][]byte{{'a', 'a'}}
+	assert.Equal([]string{}, findWords(board, []string{"aaa"}))
+
+	board = [][]byte{{'a', 'b'}, {'c', 'd'}}
+	assert.Equal([]string{"cdba"}, findWords(board, []string{"cdba"}))
+
+	board = [][]byte{
+		{'b', 'a', 'a', 'b', 'a', 'b'},
+		{'a', 'b', 'a', 'a', 'a', 'a'},
+		{'a', 'b', 'a', 'a', 'a', 'b'},
+		{'a', 'b', 'a', 'b', 'b', 'a'},
+		{'a', 'a', 'b', 'b', 'a', 'b'},
+		{'a', 'a', 'b', 'b', 'b', 'a'},
+		{'a', 'a', 'b', 'a', 'a', 'b'},
+	}
+	words := []string{
+		"aab", "bbaabaabaaaaabaababaaaaababb", "aabbaaabaaabaabaaaaaabbaaaba",
+		"babaababbbbbbbaabaababaabaaa", "bbbaaabaabbaaababababbbbbaaa",
+		"babbabbbbaabbabaaaaaabbbaaab", "bbbababbbbbbbababbabbbbbabaa",
+		"babababbababaabbbbabbbbabbba", "abbbbbbaabaaabaaababaabbabba",
+		"aabaabababbbbbbababbbababbaa", "aabbbbabbaababaaaabababbaaba",
+		"ababaababaaabbabbaabbaabbaba", "abaabbbaaaaababbbaaaaabbbaab",
+		"aabbabaabaabbabababaaabbbaab", "baaabaaaabbabaaabaabababaaaa",
+		"aaabbabaaaababbabbaabbaabbaa", "aaabaaaaabaabbabaabbbbaabaaa",
+		"abbaabbaaaabbaababababbaabbb", "baabaababbbbaaaabaaabbababbb",
+		"aabaababbaababbaaabaabababab", "abbaaabbaabaabaabbbbaabbbbbb",
+		"aaababaabbaaabbbaaabbabbabab", "bbababbbabbbbabbbbabbbbbabaa",
+		"abbbaabbbaaababbbababbababba", "bbbbbbbabbbababbabaabababaab",
+		"aaaababaabbbbabaaaaabaaaaabb", "bbaaabbbbabbaaabbaabbabbaaba",
+		"aabaabbbbaabaabbabaabababaaa", "abbababbbaababaabbababababbb",
+		"aabbbabbaaaababbbbabbababbbb", "babbbaabababbbbbbbbbaabbabaa",
+	}
+	result = findWords(board, words)
+	excepted = []string{"aab", "aabbbbabbaababaaaabababbaaba", "abaabbbaaaaababbbaaaaabbbaab", "ababaababaaabbabbaabbaabbaba"}
+	assert.Subset(excepted, result)
+	assert.Len(result, 4)
+}
