2 January 2020
LeetCode(73) -- 273, 297,
by Jerry Zhang
P273. Integer to English Words (Hard)
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
My Solution
public class P273_IntegertoEnglishWords {
String[] lessThanTwentyTable = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
"Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
String[] tensTable = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
StringBuilder sb = new StringBuilder();
if (num >= 1000000000) {
sb.append(lessThanTwentyTable[num / 1000000000 - 1]);
sb.append(" Billion");
num = num % 1000000000;
if (num > 0) {
sb.append(" ");
}
}
if (num >= 1000000) {
sb.append(convertHundreds(num / 1000000));
sb.append(" Million");
num = num % 1000000;
if (num > 0) {
sb.append(" ");
}
}
if (num >= 1000) {
sb.append(convertHundreds(num / 1000));
sb.append(" Thousand");
num = num % 1000;
if (num > 0) {
sb.append(" ");
}
}
if (num > 0) {
sb.append(convertHundreds(num));
}
return sb.toString();
}
private String convertHundreds(int num) {
StringBuilder sb = new StringBuilder();
if (num >= 100) {
sb.append(lessThanTwentyTable[num / 100 - 1]);
sb.append(" Hundred");
num = num % 100;
if (num > 0) {
sb.append(" ");
}
}
if (num > 0) {
if (num < 20) {
sb.append(lessThanTwentyTable[num - 1]);
} else {
sb.append(tensTable[num / 10 - 2]);
if (num % 10 > 0) {
sb.append(" ");
sb.append(lessThanTwentyTable[num % 10 - 1]);
}
}
}
return sb.toString();
}
}
100%
The Best Solution
class Solution {
private static String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static String[] TEN = {"","Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private static String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
public static String numberToWords(int num) {
if(num == 0) return "Zero";
String words = "";
int i = 0;
while(num > 0){
if (num % 1000!=0)
words = helper(num % 1000) + THOUSANDS[i] + " " + words;
num /= 1000;
i++;
}
return words.trim();
}
static String helper(int num){
if(num == 0) return "";
if(num < 20){
return LESS_THAN_20[num] + " ";
}else if(num < 100){
return TEN[num/10] + " " + helper(num % 10);
}else{
return LESS_THAN_20[num/100] + " Hundred " + helper(num%100);
}
}
}
Cleaner tham mine.
P297. Serialize and Deserialize Binary Tree (Hard)
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"
My Solution
public class P297_SerializeAndDeserializeBinaryTree {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "null";
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
StringBuilder sb = new StringBuilder();
boolean hasNextLevel = true;
while (hasNextLevel && queue.size() > 0) {
hasNextLevel = false;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node != null) {
sb.append(node.val).append(",");
queue.add(node.left);
queue.add(node.right);
if (node.left != null || node.right != null) {
hasNextLevel = true;
}
} else {
sb.append("null,");
queue.add(null);
queue.add(null);
}
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("null")) {
return null;
}
String[] strings = data.split(",");
TreeNode[] treeNodes = new TreeNode[strings.length];
TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
treeNodes[0] = root;
for (int i = 1; i < strings.length; i++) {
if (!strings[i].equals("null")) {
if (i % 2 != 0) {
treeNodes[i] = treeNodes[(i - 1) / 2].left = new TreeNode(Integer.parseInt(strings[i]));
} else {
treeNodes[i] = treeNodes[(i - 2) / 2].right = new TreeNode(Integer.parseInt(strings[i]));
}
}
}
return root;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(5);
P297_SerializeAndDeserializeBinaryTree obj = new P297_SerializeAndDeserializeBinaryTree();
String serialize = obj.serialize(root);
System.out.println("serialize = " + serialize);
TreeNode treeNode = obj.deserialize(serialize);
}
}
Time Limit Exceeded.
Solution
public class P297_SerializeAndDeserializeBinaryTree {
public String rserialize(TreeNode root, String str) {
// Recursive serialization.
if (root == null) {
str += "null,";
} else {
str += root.val + ",";
str = rserialize(root.left, str);
str = rserialize(root.right, str);
}
return str;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return rserialize(root, "");
}
public TreeNode rdeserialize(List<String> l) {
// Recursive deserialization.
if (l.get(0).equals("null")) {
l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(l.get(0)));
l.remove(0);
root.left = rdeserialize(l);
root.right = rdeserialize(l);
return root;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] data_array = data.split(",");
List<String> data_list = new LinkedList<>(Arrays.asList(data_array));
return rdeserialize(data_list);
}
}
13%
The Best Solution
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
recursiveDFSSerialize(root,sb);
return sb.toString();
}
private void recursiveDFSSerialize(TreeNode root, StringBuilder sb){
if (root == null){
sb.append("#");
return;
}
sb.append((char)(root.val + '0'));
recursiveDFSSerialize(root.left,sb);
recursiveDFSSerialize(root.right,sb);
}
int index = 0;
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
return recursiveDFSDeserialize(data.toCharArray());
}
private TreeNode recursiveDFSDeserialize(char[] data){
if (data[index] == '#'){
index++;
return null;
}
TreeNode root = new TreeNode(data[index++] - '0');
root.left = recursiveDFSDeserialize(data);
root.right = recursiveDFSDeserialize(data);
return root;
}
}
P472. Concatenated Words (Hard)
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
My Solution
public class P472_ConcatenatedWords {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
HashSet<String> set = new HashSet<>(Arrays.asList(words));
List<String> ans = new ArrayList<>();
for (String word : words) {
set.remove(word);
if (concatenate(word, set)) {
ans.add(word);
}
set.add(word);
}
return ans;
}
private boolean concatenate(String s, HashSet<String> set) {
if (set.contains(s)) {
return true;
}
for (int i = 0; i < s.length(); i++) {
String substring = s.substring(0, i);
if (set.contains(substring)) {
if (concatenate(s.substring(i), set)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
List<String> allConcatenatedWordsInADict =
new P472_ConcatenatedWords().findAllConcatenatedWordsInADict(
new String[]{"cat", "cats", "catsdogcats", "dog", "dogcatsdog",
"hippopotamuses", "rat", "ratcatdogcat"});
System.out.println("allConcatenatedWordsInADict = " + allConcatenatedWordsInADict);
}
}
StackOverflowError
Discuss
DP
public class Solution {
public static List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> result = new ArrayList<>();
Set<String> preWords = new HashSet<>();
Arrays.sort(words, new Comparator<String>() {
public int compare (String s1, String s2) {
return s1.length() - s2.length();
}
});
for (int i = 0; i < words.length; i++) {
if (canForm(words[i], preWords)) {
result.add(words[i]);
}
preWords.add(words[i]);
}
return result;
}
private static boolean canForm(String word, Set<String> dict) {
if (dict.isEmpty()) return false;
boolean[] dp = new boolean[word.length() + 1];
dp[0] = true;
for (int i = 1; i <= word.length(); i++) {
for (int j = 0; j < i; j++) {
if (!dp[j]) continue;
if (dict.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}
31%
The Best Solution
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> hset = new HashSet<>(10000);
List<String> l = new ArrayList<>();
int min=Integer.MAX_VALUE;
for(String s:words){
if(s.length()==0) continue;
hset.add(s);
min=Math.min(min,s.length());
}
for(String s:words){
if(check(hset,s,0,min)) l.add(s);
}
return l;
}
public boolean check(Set<String> hset,String w,int start,int min){
for(int i=start+min; i<=w.length()-min;i++){
if(hset.contains(w.substring(start,i)) &&(hset.contains(w.substring(i)) ||
check(hset,w,i,min))) return true;
}
return false;
}
}