Because in the problem it mentioned "A word's abbreviation is unique if no other word from the dictionary has the same abbreviation." As a result, only words that are different than the target word need to be checked for uniqueness.
luke.wang.7509
@luke.wang.7509
Posts made by luke.wang.7509

RE: Wrong test case?

RE: My Java solution without setting the peeked value to null
Yes, you are right. If we want to set it to null we have to declare the peekValue using Integer instead of int.

My Java solution without setting the peeked value to null
In my solution I have three variables which are a iterator, a integer peek value and a boolean value indicating whether the iterator is empty. The small trick here is I store the current value of the iterator in the peek value and let the iterator point to the next possible value. Since there could be no next value, using hasNext() function will not correctly checked whether the peeking iterator is empty so I use a boolean variable to help indicate whether the iterator has no next value or not. Below is my code in Java:
// Java Iterator interface reference: // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html class PeekingIterator implements Iterator<Integer> { private Iterator<Integer> _iterator; private Integer peekVal=null; private boolean empty; public PeekingIterator(Iterator<Integer> iterator) { // initialize any member here. this._iterator = iterator; this.empty = !iterator.hasNext(); this.peekVal = iterator.next(); } // Returns the next element in the iteration without advancing the iterator. public Integer peek() { return peekVal; } // hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. @Override public Integer next() { int result = peekVal; if(_iterator.hasNext()) peekVal = _iterator.next(); else { empty=true; peekVal=null; } return result; } @Override public boolean hasNext() { return !empty; } }

RE: Simple and fast Java solution with explanation
This is because when n is 2147483647, n+1 will be 2147483648 which will ticks over to 2147483648. So I just make it a separate & operation after the for loop in case the i ticks over

Java Easy Understand O(n) Solution
The basic idea of this problem is to compute all the ugly numbers in sequence and count to the given number of k ugly numbers. The way I approached this problem is first I have a arraylist to store the ugly numbers in sequence. Then I declared three counter variables: a,b,and c which represent the corresponding index in the arraylist for the multiplier of 2,3,and 5. Since each previous ugly number times one of the multiplier will produce a new ugly number, I start from the starting index 0 and multiply the ugly number at that index with each multiplier and get the smallest product which is the next ugly number from the three. The corresponding multipliers' index will be incremented by one and we do this recursively until we have K ugly numbers. Here is the code implementation in Java:
public class Solution { public int nthUglyNumber(int n) { if(n<=0) return 0; int a=0,b=0,c=0; List<Integer> table = new ArrayList<Integer>(); table.add(1); while(table.size()<n) { int next_val = Math.min(table.get(a)*2,Math.min(table.get(b)*3,table.get(c)*5)); table.add(next_val); if(table.get(a)*2==next_val) a++; if(table.get(b)*3==next_val) b++; if(table.get(c)*5==next_val) c++; } return table.get(table.size()1); } }

Java. not using DP, average O(n) time complexity and O(1) space complexity solution
My solution is based on the greedy algorithm. The basic idea is when we are examining an index, we want to find the index that is within the range of the current index and can reach the farthest distance. We find that index and perform the same procedure until we can at least reach the end(we can reach more than the last index). A count variable will be maintained when we jump indexes and the count value will be the minimal count value. Here is my code in Java:
public class Solution { public int jump(int[] nums) { if(nums.length<=1) return 0; int distance=nums[0]; int steps=1; for(int i=0;i<nums.length;) { if(distance>=nums.length1) return steps; int new_distance=distance; int iter=i+1; int next_index=iter; steps++; while(iter<nums.length && iter<=i+nums[i]) { if(iter+nums[iter]>new_distance) { new_distance=iter+nums[iter]; next_index=iter; } iter++; } if(new_distance==distance) return 1; distance=new_distance; i=next_index; } return steps; } }

Easy to understand Java O(n) solution
The basic idea is to start from the first index, check whether the remaining gas(gascost) is positive. If so, continue to the next index. If not, the starting index can only be the indexes after the current index. We allow the iterator to reach 2the length of array gas so that when the iterator meet with the starting index, we find a valid index. Otherwise, if the iterator exceed 2the length of the array, there are no valid staring index and we return 1. Here is my code in Java:
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if(cost.length==0) return 1; int remaining=1; int start_i=0; int i=0; while(i<2*gas.length) { int index=i%gas.length; if(remaining<0) { if(gas[index]>=cost[index]) { remaining=gas[index]cost[index]; start_i=index; } } else { if(start_i==index) return start_i; remaining+=gas[index]cost[index]; } i++; } return 1; } }

Java easy to understand two stacks solution
The difficult of this problem is how to get the min element from stack in constant time. The way I approach this problem is to use another stack(min stack) which records a sequence of minimal values as elements being pushed into the stack. In this way, we can be sure that the top element on the stack must be the minimal element. Finally, we maintaining the stack's min element up to date by checking whether the top element in the min stack is the same with the top element in the normal stack. If there are the same, we pop both stack. Otherwise, we only pop the normal stack.
class MinStack { private Stack<Integer> st = new Stack<Integer>(); private Stack<Integer> min_st = new Stack<Integer>(); public void push(int x) { if(min_st.isEmpty()  min_st.peek()>=x) min_st.push(x); st.push(x); } public void pop() { if((int)st.peek()==(int)min_st.peek()) min_st.pop(); st.pop(); } public int top() { return st.peek(); } public int getMin() { return min_st.peek(); } }

Simple and fast Java solution with explanation
For this problem, the naive approach is to iterate from n to m and & all the values. However, this approach is time consuming because it waste time to & values which will eventually be 0. The insight of this problem is that we can be sure the value & from n to m will be 0 if the index of the highest 1 in n's binary representation is different from the index of the highest 1 in m's binary representation. For example if we have n=001 and m=110, we will have two value in between which could be 001 and 100 and these two & will be 0 which makes the whole value 0. Here goes my code in java, hope it will explain itself:
public class Solution { public int rangeBitwiseAnd(int m, int n) { int p1=0, p2=0; int val1=m, val2=n; while(val1>1  val2>1) { if(val1>1) { val1=val1/2; p1++; } if(val2>1) { val2=val2/2; p2++; } } if(p1!=p2) return 0; int result=~0; for(int i=m;i<n;i++) result=result&i; result=result&n; return result; } }

Java simple O(n) Solution
The basic idea of this program is to recursively compute the height of the left subtree and of the right subtree. If the returned two heights' are both positive and their difference is less or equal to 1, return the larger height. Otherwise, return 1 which indicates there existing heights' differ than 1.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { return compareHeight(root,0)>=0; } public int compareHeight(TreeNode node, int h) { if(node==null) return h; int left_h = compareHeight(node.left,h+1); int right_h = compareHeight(node.right,h+1); return (left_h>=0 && right_h>=0 && Math.abs(left_hright_h)<=1)?Math.max(left_h,right_h):1; } }