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; } }

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; } }