Leetcode 953. Verifying an Alien Dictionary Java solution


class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int n = words.length;
        Map<Character, Integer> orderMap = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            orderMap.put(order.charAt(i),i);
        }
        for (int i = 0; i < n - 1; i++) {
            if (!isSorted(words[i], words[i + 1], orderMap)) {
                return false;
            }
        }
        return true;
    }
    boolean isSorted(String first, String two, Map<Character, Integer> map) {
        int len1 = first.length();
        int len2 = two.length();
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            int o1 = map.get(first.charAt(i));
            int o2 = map.get(two.charAt(j));
            if ( o1 < o2) {
                return true;
            } else if (o1 == o2) {
                i++;
                j++;
            } else {
                return false;
            }
        }
        return i == len1;
    }
}

Comments

Post a Comment

Popular posts from this blog

Can I name a method with the same name of the class in Java?

Can a class have a method with the same name of the class in Java? The answer is yes. See the example below. Public class MyClass { public MyClass() { } public void MyClass() { System.out.println("I have the same name as the class!"); } } You could definitely name a method with the name of the class. As a rule of thumb, you should not capitalize the first letter of the name of your method, though.
Read more

What is new in Java 8

1.  There are default methods and static methods in interfaces in Java 8. 2. Lamdas   Collections . sort ( list , ( o1 , o2 ) -> o1 . getTime () - o2 . getTime ()); Pre-Java8 Collections . sort ( list , new Comparator < Message >() { @Override public int compare ( Message o1 , Message o2 ) { return o1 . getTime () - o2 . getTime (); } });
Read more

Quicksort Java implementation

import java.util.Arrays; public class QuickSort { int [] data ; public void quicksort( int [] nums) { if (nums == null || nums. length == 0 ) return ; data = nums; sort( 0 , nums. length - 1 ); } private void sort( int left, int right) { if (right <= left) return ; int pivot = partition(left, right); sort(left, pivot - 1 ); sort(pivot + 1 , right); } /** * put all the numbers that are smaller than pivot to the left * **/ int partition( int left, int right) { int pivot = data [right]; int startIndex = left; for ( int i = left; i < right; i++) { //all the nums on the left of startIndex are smaller than pivot //the number at startIndex is >= pivot if ( data [i] < pivot) { swap(startIndex++, i); } } // put the pivot to the right position swap(startIndex, right); r...
Read more