leetcode Nested List Weight Sum

https://leetcode.com/problems/nested-list-weight-sum/

Problem

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1’s at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)

Solution

A recursive implementation and looks like back tracking on depth.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class Solution {
    int depth = 1;
    int sum = 0;
    public int depthSum(List<NestedInteger> nestedList) {
        for(NestedInteger n : nestedList) {
            if(n.isInteger())
                sum += n.getInteger() * depth;
            else {
                depth++;
                depthSum(n.getList());
                depth--;
            }
        }
        return sum;
    }
}

318. Maximum Product of Word Lengths

https://leetcode.com/problems/maximum-product-of-word-lengths/

 

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

 

Solution:

The intuition for solving this problem is to compare each pair of words. The complexity of iterating each pair of words is O(n^2). If we compare each character in two words, there will be an additional O(k^2) complexity. (n is the number of words, k is the  length of a word).

Thus, The brutal force solution is time consuming. So we need to find out a way to decrease the complexity of previous two steps. The comparison between each two words is hard to optimize, since the words are arbitrary. However, there is a trick we can do on the comparison of characters in each word.

The idea is use an integer’s lower 26 bits to present a character of a word. if a character exists in a word, the bit that represent that word will be 1, otherwise 0. Thus, after this pre-processing, when we and any two integers, if there do not have same characters, the result will be 0, otherwise will be 1.

Hence, the complexity of character’s comparison will be O(1), which make the whole time complexity be O(n^2). This is acceptable.

Here is the code:

/*
bit manipulation.

*/
public class Solution {
    public int maxProduct(String[] words) {
        int len = words.length;
        int max = 0;
        if(len == 0) return 0;
        int[] biVals = new int[len];
  // pre-processing each word, use an integer's lower 26 bits to present a word's characters.
        for(int i = 0; i < len; i++) {
            biVals[i] = 0;
            for(char ch : words[i].toCharArray()) {
                biVals[i] |= 1 << (ch - 'a');
            }
        }
    // compare each pair of words in O(n^2).
        for( int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {                 if(((biVals[i] & biVals[j]) == 0) && (words[i].length() * words[j].length() > max))
                    max = words[i].length() * words[j].length();
            }
        }
        return max;
    }
}

 

 

 

Leetcode 284. Peeking Iterator

https://leetcode.com/problems/peeking-iterator/

 

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

 

Solutions:

Here I come up with two solutions. One is according to Google’s guava library source code.

The other one is using List, which may be slower, because we need to load all element in the iterator when we construct the class.

solution1:

class PeekingIterator implements Iterator<Integer> {
    Iterator it;
    int peek;
    boolean peeked;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    it = iterator;
	}

    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
	    if(!peeked) {
	        peek = (int)it.next();
	        peeked = true;
	    }

        return peek;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    if(!peeked) return (int)it.next();
	    int result = peek;
	    peeked = false;
	    return result;
	}

	@Override
	public boolean hasNext() {
	    return peeked || it.hasNext();
	}
}

 

solution2:

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    List<Integer> iteratorList = new ArrayList<>();
    int pointer;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    pointer = 0;
	    while(iterator.hasNext()) {
	        iteratorList.add(iterator.next());
	    }
	}

    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return iteratorList.get(pointer);
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    return iteratorList.get(pointer++);
	}

	@Override
	public boolean hasNext() {
	    return pointer < iteratorList.size();
	}
}

leetcode 288. Unique Word Abbreviation

https://leetcode.com/problems/unique-word-abbreviation/

 

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

Solution:

First solution is that use a set of String for an abbr. HashMap<String, Set<String>> abbrDictionary;

The improvement is that when a duplicate happens, use a null to present the value of a abbr. HashMap<String, String> abbrDictionary;

public class ValidWordAbbr {
    HashMap<String, Set<String>> abbrDictionary;
    public ValidWordAbbr(String[] dictionary) {
        abbrDictionary = new HashMap<>();
        for(String word : dictionary) {
            String key = getKey(word);
            if(!abbrDictionary.containsKey(key)) abbrDictionary.put(key, new HashSet<String>());
            abbrDictionary.get(key).add(word);
        }
    }

    public boolean isUnique(String word) {
        String key = getKey(word);
        return !abbrDictionary.containsKey(key)|| (abbrDictionary.get(key).size() ==1 && abbrDictionary.get(key).contains(word));
    }

     private String getKey(String str){
        if(str.length()<=2) return str;
        return str.charAt(0)+Integer.toString(str.length()-2)+str.charAt(str.length()-1);
    }

}

// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");

public class ValidWordAbbr {
    HashMap<String, String> map;
    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<String, String>();
        for(String str:dictionary){
            String key = getKey(str);
            // If there is more than one string belong to the same key
            // then the key will be invalid, we set the value to ""
            if(map.containsKey(key)){
                if(!map.get(key).equals(str)){
                    map.put(key, "");
                }
            }
            else{
                map.put(key, str);
            }
        }
    }

    public boolean isUnique(String word) {
        return !map.containsKey(getKey(word))||map.get(getKey(word)).equals(word);
    }

    String getKey(String str){
        if(str.length()<=2) return str;
        return str.charAt(0)+Integer.toString(str.length()-2)+str.charAt(str.length()-1);
    }
}

// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");

hackerrank: Breadth First Search: Shortest Reach

Problem:

https://www.hackerrank.com/challenges/bfsshortreach

Analysis:

Just a implementation of bfs.

 

Solution:

 

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static List[] graph;

    @SuppressWarnings("unchecked")
	public static void addToGraph(int node1, int node2) {
        if(graph[node1] == null) graph[node1] = new ArrayList<Integer>();
        if(!graph[node1].contains(node2))
        	graph[node1].add(node2);
        if(graph[node2] == null) graph[node2] = new ArrayList<Integer>();
        if(!graph[node2].contains(node1))
        graph[node2].add(node1);
    }    

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int num_cases = in.nextInt();
        for(int c = 0; c < num_cases; c++) {
    	int num_nodes = in.nextInt(), num_edge = in.nextInt();
        graph = new List[num_nodes+1];
    	for(int i = 0; i < num_edge; i++) {
            addToGraph(in.nextInt(), in.nextInt());
        }
    		List<Integer> result = new ArrayList<>();
            int startNode = in.nextInt(); //get the start node.

            // print the graph for test
            /*
            System.out.println("This is the graph represented using adjacent lists");
            for(int x = 0; x < graph.length; x++) {                 System.out.print(x + "--> ");
                System.out.println(graph[x]);
            }*/

            // get the shortest distance for each destinationNode.
            for(int destinationNode = 1; destinationNode <= num_nodes; destinationNode++){
                if(destinationNode == startNode) continue;
                /*if(graph[destinationNode] == null) {
                	if(destinationNode == num_nodes) System.out.println(-1);
                	else System.out.println(-1 + " ");
                }*/
                boolean[] visited = new boolean[num_nodes+1];// to mark visited node for avoiding cycle.
                Deque<Integer> queue = new ArrayDeque<>();
                queue.addLast(startNode);
                visited[startNode] = true;
                int distance = 0;
                boolean gotPath = false;
                while(!queue.isEmpty()) {
                    int levelSize = queue.size();
                    for(int j = 0; j < levelSize; j++) {
                        int curNode = queue.removeFirst();
                        if(curNode == destinationNode){
                            result.add(distance);
                            gotPath = true;
                            break;
                        }else{
                                for(int k = 0;graph[curNode] != null && k < graph[curNode].size(); k++){
                                	int nextNode = (int)graph[curNode].get(k); // why need we cast to int?
                                	if(!visited[nextNode]){
                                		queue.addLast(nextNode);
                                		visited[nextNode] = true;
                                	}
                                }
                            }
                        }
                    distance += 6;
                    }
                	if(!gotPath) result.add(-1);
                }
	        	for(int n = 0; n < result.size()-1; n++) {
	        		System.out.print(result.get(n) + " ");
	        	}
	        	System.out.print(result.get(result.size()-1));
	            System.out.println();
            }
            System.out.println();
        }

}

Leetcode. 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are

["1->2->5", "1->3"]

Solution 1:

Basically, to solve this problem, we need traversal all the nodes in the tree. Hence, no matter in what order, the time complexity is O(n).

This is my first solution, which still can be improved. Firstly, we can try to change the way of concatenation to avoid delete “->” on the leaf node. Secondly, string concatenation may be too expensive, so we can use stringBuilder to improve the performance.

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if(root == null) return result;
getPath(root, "", result);
return result;
}
private void getPath(TreeNode node, String path, List<String> result) {
path += node.val + "->";
if(node.left != null) getPath(node.left, path, result);
if(node.right != null) getPath(node.right, path, result);
if(node.left == null && node.right == null){
path = path.substring(0, path.length()-2);
result.add(path);
}
// System.out.println(path);
}
}

Change the way of string concatenation.

public List<String> binaryTreePaths(TreeNode root) {
    List<String> answer = new ArrayList<String>();
    if (root != null) searchBT(root, "", answer);
    return answer;
}
private void searchBT(TreeNode root, String path, List<String> answer) {
    if (root.left == null && root.right == null) answer.add(path + root.val);
    if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
    if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
}

Use StringBuilder. It is tricky to decide when to append the node.val and “->”.

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        helper(res, root, sb);
        return res;
    }

    private void helper(List<String> res, TreeNode root, StringBuilder sb) {
        if(root == null) {
            return;
        }
        int len = sb.length();
        sb.append(root.val);
        if(root.left == null && root.right == null) {
            res.add(sb.toString());
        } else {
            sb.append("->");
            helper(res, root.left, sb);
            helper(res, root.right, sb);
        }
        sb.setLength(len);
    }