我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 820. 單詞的壓縮編碼

題目

給定一個單詞列表，我們將這個列表編碼成一個索引字元串 S 與一個索引列表 A。

例如，如果這個列表是 ["time", "me", "bell"]，我們就可以將其表示為 S = "time#bell#" 和 indexes = [0, 2, 5]。

對於每一個索引，我們可以通過從字元串 S 中索引的位置開始讀取字元串，直到 "#" 結束，來恢復我們之前的單詞列表。

那麼成功對給定單詞列表進行編碼的最小字元串長度是多少呢？

示例：

輸入: words = ["time", "me", "bell"]
輸出: 10
說明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 7
• 每個單詞都是小寫字母 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/short-encoding-of-words
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

• 分析完題目後發現，只要有相同尾碼的都可以合併只統計較長的那個字元串長度並加1（#占一個長度）
• 問題在於如何去判斷一堆字元串是否某幾個有相同尾碼，比較容易想到的是endWiths()和indexOf()兩個方法，原理類似，但效率太低；
• endwiths()和indexOf()慢在每次每個字元都需要一次全掃描，如果能一次掃描並記錄效率將成倍提升，所以更高效的是構造並記錄索引，即Trie（單詞查找樹/字典樹）；

思路1-使用endwitchs()或indexOf()判斷是否有相同尾碼

步驟：

1. 對所有單詞按長度降序排序；
2. 一次遍歷，將單詞追加到StringBuilder並每次額外追加一個#，追加的前提條件是StringBuilder中indexOf(當前單詞+#)結果為-1；
3. 返回StringBuilder的長度即為結果；

思路2-構造Trie，需要構造節點

步驟：

1. 對所有單詞按長度降序排序，定義節點Node類，持有一個26長度的Node數組，26個數對應a到z；
2. 依次取每個單詞，倒序遍歷每個字元，並構造字典樹，若需要新建節點說明是新單詞，構造完統計其長度加1，若無需構造節點說明該單詞是某個單詞的尾碼，不統計其長度；
3. 累加統計的新單詞長度即結果；

Trie樹實際上是一顆每層都有26個子節點的多叉樹，其實跟二叉樹是一樣的邏輯，只不過層節點變多了

演算法源碼示例

package leetcode;

import java.util.Arrays;

/**
 * @author ZhouJie
 * @date 2020年3月28日 下午9:53:38 
 * @Description: 820. 單詞的壓縮編碼
 *
 */
public class LeetCode_0820 {

}

class Solution_0820 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年3月28日 下午9:54:12 
	 * @param: @param words
	 * @param: @return
	 * @return: int
	 * @Description: 1-按長度降序排序，然後拼接，使用indexof()
	 *
	 */
	public int minimumLengthEncoding_1(String[] words) {
		// 按長度降序排序
		Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
		StringBuilder sb = new StringBuilder();
		for (String s : words) {
			if (sb.indexOf(s + "#") == -1) {
				sb.append(s).append("#");
			}
		}
		return sb.length();
	}

	/**
	 * @author ZhouJie
	 * @date 2020年3月29日 上午1:33:22 
	 * @Description: 輔助索引節點
	 *
	 */
	class TailNode {
		TailNode[] next = new TailNode[26];
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年3月29日 上午1:33:24 
	 * @param: @param words
	 * @param: @return
	 * @return: int
	 * @Description: 2-Tail，建立字典索引
	 *
	 */
	public int minimumLengthEncoding_2(String[] words) {
		// 按長度降序排序
		Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
		int minLen = 0;
		// 根索引
		TailNode root = new TailNode();
		for (String s : words) {
			// 每次都從根開始搜索
			TailNode currNode = root;
			// 當前單詞是否需要單獨新建索引
			boolean f = false;
			for (int i = s.length() - 1; i > -1; i--) {
				int index = s.charAt(i) - 'a';
				// 當前字元是否已建立索引，若未建立索引則新建索引並更新布爾值
				if (currNode.next[index] == null) {
					f = true;
					currNode.next[index] = new TailNode();
				}
				// 搜索下一個索引
				currNode = currNode.next[index];
			}
			if (f) {
				// 記錄新建索引增加的長度
				minLen += s.length() + 1;
			}
		}
		return minLen;
	}

}