algorithm001 · GeekUniversity · May 13, 2019 · May 11, 2019
diff --git a/Week_04/id_9/LeetCode_211_9.cs b/Week_04/id_9/LeetCode_211_9.cs
@@ -0,0 +1,103 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace ProblemSolutions
+{
+    public class Problem211 : IProblem
+    {
+        public void RunProblem()
+        {
+            WordDictionary obj = new WordDictionary();
+            obj.AddWord("bad");
+            obj.AddWord("dad");
+            obj.AddWord("mad");
+            bool param_2 = obj.Search("pad");
+            param_2 = obj.Search("bad");
+            param_2 = obj.Search(".ad");
+            param_2 = obj.Search("b..");
+            param_2 = obj.Search("b.d");
+        }
+
+        public class WordDictionary
+        {
+            public class TrieNode
+            {
+                public TrieNode(char c)
+                {
+                    m_char = c;
+                }
+                public char m_char;
+                public bool m_isWord;
+                public TrieNode[] m_nextNode = new TrieNode[26];
+            }
+
+            private TrieNode rootNode = new TrieNode('\\');
+
+            /** Initialize your data structure here. */
+            public WordDictionary()
+            {
+
+            }
+
+            /** Adds a word into the data structure. */
+            public void AddWord(string word)
+            {
+                var nodeTemp = rootNode;
+                foreach (var wordItem in word)
+                {
+                    var charIndex = wordItem - 'a';
+                    if (nodeTemp.m_nextNode[charIndex] == null)
+                        nodeTemp.m_nextNode[charIndex] = new TrieNode(wordItem);
+
+                    nodeTemp = nodeTemp.m_nextNode[charIndex];
+                }
+                nodeTemp.m_isWord = true;
+            }
+
+            /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
+            public bool Search(string word)
+            {
+                return RecurSive(rootNode, word, -1);
+            }
+
+            private bool RecurSive(TrieNode node, string word, int charIndex)
+            {
+                //查看当前节点满足的条件
+                if (charIndex > word.Length - 1) return false;
+                if (charIndex == word.Length - 1) return node.m_isWord && (node.m_char == word[charIndex] || word[charIndex] == '.');
+
+                //查看下一个节点满足的条件
+                var curChar = word[charIndex + 1];
+                if (curChar == '.')
+                {
+                    foreach (var nodeItem in node.m_nextNode)
+                    {
+                        var isOk = false;
+                        if (nodeItem != null)
+                            isOk = RecurSive(nodeItem, word, charIndex + 1);
+
+                        if (isOk) return true;
+                    }
+                }
+                else
+                {
+                    var cIndex = curChar - 'a';
+                    if (node.m_nextNode[cIndex] != null)
+                        return RecurSive(node.m_nextNode[cIndex], word, charIndex + 1);
+                }
+
+                return false;
+            }
+        }
+
+        /**
+         * Your WordDictionary object will be instantiated and called as such:
+         * WordDictionary obj = new WordDictionary();
+         * obj.AddWord(word);
+         * bool param_2 = obj.Search(word);
+         */
+    }
+}
diff --git a/Week_04/id_9/LeetCode_720_9.cs b/Week_04/id_9/LeetCode_720_9.cs
@@ -0,0 +1,123 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace ProblemSolutions
+{
+    public class Problem720 : IProblem
+    {
+        public void RunProblem()
+        {
+            string[] words = new string[] { "a", "apple", "b", "be", "bee", "beer" };
+            var temp = LongestWord(words);
+        }
+
+        public string LongestWord(string[] words)
+        {
+            /*
+             * 实现思路：
+             * 1.使用数据源来“喂养”TrieTree
+             * 2.再让TrieTree告知我们，满足题目需求的结果
+             * 
+             * 时间复杂度：输入的单词，是要遍历一次的，构建trieTree，然后要拿到结果，还是要做回溯的，那么是对树所有节点又遍历一次
+             * 空间复杂度：主要是TrieTree占用的存储空间
+             * 
+             * 使用此种方式，其实就是数据源越大越是有利
+             */
+
+            var trieTree = new TrieTree();
+
+            foreach (var wordItem in words)
+                trieTree.AddWord(wordItem);
+
+            return trieTree.GetLongestWord();
+        }
+
+        public class TrieTree
+        {
+            public class TrieNode
+            {
+                public string m_words;
+                public TrieNode[] m_nextIndex = new TrieNode[26];
+                public bool m_isWord;
+            }
+
+            private TrieNode m_rootNode = new TrieNode();
+
+            public void AddWord(string word)
+            {
+                var trieNodeTemp = m_rootNode;
+                foreach (var wordItem in word)
+                {
+                    var intTemp = wordItem - 'a';
+
+                    if (trieNodeTemp.m_nextIndex[intTemp] == null)
+                        trieNodeTemp.m_nextIndex[intTemp] = new TrieNode();
+
+                    trieNodeTemp = trieNodeTemp.m_nextIndex[intTemp];
+                }
+                trieNodeTemp.m_isWord = true;
+                trieNodeTemp.m_words = word;
+            }
+
+            public string GetLongestWord()
+            {
+                Recursive(m_rootNode, -1);
+                return longestWord;
+            }
+
+            private int longest = 0;
+            private string longestWord = "";
+            private void Recursive(TrieNode node, int length)
+            {
+                length++;
+
+                if (node.m_isWord && length > longest)
+                {
+                    longest = length;
+                    longestWord = node.m_words;
+                }
+
+                for (int i = 0; i < node.m_nextIndex.Length; i++)
+                {
+                    if (node.m_nextIndex[i] != null && node.m_nextIndex[i].m_isWord)
+                    {
+                        Recursive(node.m_nextIndex[i], length);
+                    }
+                }
+            }
+        }
+
+        public string LongestWord1(string[] words)
+        {
+            /*
+             * 思路：
+             * 1.结果要求按照字典序来处理相同长度的单词，那么就先对数组做字典序排序，复杂度：O(nlogn);
+             * 2.遍历新的数组，寻找满足条件的最长单词
+             * 
+             * 时间复杂度：O(nlogn + n)，但是还要考虑到字符串比较的复杂度才行，字符串比较，应该是使用简单的比较方法才对
+             * 空间复杂度：O(n)，因为会把所有的单词存入到set中去
+             */
+
+            var forReturn = "";
+            HashSet<string> sets = new HashSet<string>();
+
+            var sortedArray = words.OrderBy(i => i);
+
+            foreach (var arrayItem in sortedArray)
+            {
+                if (arrayItem.Length == 1 || sets.Contains(arrayItem.Substring(0, arrayItem.Length - 1)))
+                {
+                    if (forReturn.Length < arrayItem.Length)
+                        forReturn = arrayItem;
+
+                    sets.Add(arrayItem);
+                }
+            }
+
+            return forReturn;
+        }
+    }
+}
diff --git a/Week_04/id_9/NOTE.md b/Week_04/id_9/NOTE.md
@@ -1 +1,7 @@
-# 学习笔记
+# 学习笔记
+1. 本次主要是练习TrieTree相关的题目，一个简单的一个中等的；
+2. 两个题，其实都用到的是：TrieTree的构建+回溯法
+3. 当需要尝试各种可能性时，使用回溯法是很不错的；
+4. 第1题，要找出满足条件的最长字符串，不遍历一遍TrieTree，是不会知道最长的字符串的
+5. 第2题，相当于做的是模糊匹配，有多种可能的匹配方式，只要一种匹配尝试成功了就是成功
+6. TrieTree是很实用的，构建也是相当简单的，单个的Trie节点，可以携带业务信息来加速查找，比如“是否是单词”，“当前字符是什么”，“若是一个单词，那么这个单词是什么”