LIKE CODING

Friday, April 2, 2021

LeetCode [1570] Dot Product of Two Sparse Vectors

1570. Dot Product of Two Sparse Vectors

Medium

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

Constraints:

n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100

class SparseVector {
    Map<Integer, Integer> map;
    SparseVector(int[] nums) {
        map = new HashMap<>();
        for(int i=0; i<nums.length; ++i){
            map.put(i, nums[i]);
        }
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sz1 = map.size();
        int sz2 = vec.map.size();
        if(sz1<sz2) return helper(map, vec.map);
        else return helper(vec.map, map);
    }
    
    int helper(Map<Integer, Integer> map1, Map<Integer, Integer> map2){
        int s = 0;
        for(Map.Entry<Integer, Integer> en : map1.entrySet()){
            int index = en.getKey();
            int value = en.getValue();
            if(map2.containsKey(index)){
                s += value*map2.get(index);
            }
        }
        return s;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);

Thursday, April 1, 2021

LeetCode [680] Valid Palindrome II

680. Valid Palindrome II

Easy

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

class Solution {
    public boolean validPalindrome(String s) {
        int n = s.length(), l = 0, r = n-1, d = 0;
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)){
                return helper(s, l+1, r)||helper(s, l, r-1);
            }
            l++;
            r--;
        }
        return true;
    }
    
    boolean helper(String s, int l, int r){
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

LeetCode [1249] Minimum Remove to Make Valid Parentheses

1249. Minimum Remove to Make Valid Parentheses

Medium

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

class Solution {
    public String minRemoveToMakeValid(String s) {
        String s1 = trim1(s);
        String s2 = trim2(new StringBuilder(s1).reverse().toString());
        return new StringBuilder(s2).reverse().toString();
    }
    
    String trim1(String s){
        int l = 0, r = 0;
        StringBuilder sb = new StringBuilder();
        for(char ch : s.toCharArray()){
            boolean skip = false;
            if(ch=='(') l++;
            if(ch==')'){
                r++;
                if(r>l){
                    skip = true;
                    r--;
                } 
            }
            if(!skip) sb.append(ch);
        }
        return sb.toString();
    }
    
    String trim2(String s){
        int l = 0, r = 0;
        StringBuilder sb = new StringBuilder();
        for(char ch : s.toCharArray()){
            boolean skip = false;
            if(ch==')') r++;
            if(ch=='('){
                l++;
                if(l>r){
                    skip = true;
                    l--;
                }
            }
            if(!skip) sb.append(ch);
        }
        return sb.toString();
    }
}

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stk = new Stack<>();
        StringBuilder sb = new StringBuilder(s);
        int n = sb.length();
        for(int i=0; i<n; ++i){
            if(s.charAt(i)=='('){
                stk.add(i);
            }else if(s.charAt(i)==')'){
                if(!stk.isEmpty()){
                    stk.pop();
                }else{//extra ')', remove
                    sb.setCharAt(i, '*');
                }
            }
        }

        while(!stk.isEmpty()){
            int i = stk.pop();
            sb.setCharAt(i, '*');
        }

        return sb.toString().replaceAll("\\*", "");
    }
}

LeetCode [1428] Leftmost Column with at Least a One

1428. Leftmost Column with at Least a One

Medium

(This problem is an interactive problem.)

A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.

You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
BinaryMatrix.dimensions() returns the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes, the input will be the entire binary matrix mat. You will not have access to the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is either 0 or 1.
mat[i] is sorted in non-decreasing order.

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface BinaryMatrix {
 *     public int get(int row, int col) {}
 *     public List<Integer> dimensions {}
 * };
 */

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dm = binaryMatrix.dimensions();
        int m = dm.get(0), n = dm.get(1);
        
        int leftMost = n;
        for(int i=0; i<m; ++i){
            int l = left(i, m, n, binaryMatrix);
            leftMost = Math.min(leftMost, l);
        }
        return leftMost==n ? -1 : leftMost;
    }
    
    int left(int row, int m, int n, BinaryMatrix binaryMatrix){
        int l = 0, r = n-1;
        while(l<=r){
            int mid = (l+r)/2;
            int midV = binaryMatrix.get(row, mid);
            if(midV==1){
                if(mid==l) return mid;
                r = mid;
            }else{
                if(mid==r) return n;
                l = mid+1;
            }
        }
        return n;
    }
}

LeetCode [953] Verifying an Alien Dictionary

953. Verifying an Alien Dictionary

Easy

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are English lowercase letters.

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i=0; i<order.length(); ++i) map.put(order.charAt(i), i);

        int i = 0;
        boolean cont = true;

        while(cont){
            cont = false;
            char ch0 = '.';
            String pref0 = "";
            for(String w : words){
                int len = w.length();
                if(i<len){
                    cont = true;
                    String pref1 = w.substring(0, i);
                    char ch1 = w.charAt(i);
                    if(pref0.equals(pref1)){
                        if(ch0!='.' && ch0!=ch1){
                            //ch0 < ch
                            if(map.get(ch0) > map.get(ch1)) return false;
                        }
                    }
                    pref0 = pref1;
                    ch0 = ch1;
                }else if(i==len){
                    String pref1 = w;
                    char ch1 = '.';
                    if(pref0.equals(pref1) && ch0!='.') return false;
                    pref0 = pref1;
                    ch0 = ch1;
                }
            }
            i++;
        }

        return true;
    }
}

class Solution {
  public boolean isAlienSorted(String[] words, String order) {
    Map<Character, Integer> map = new HashMap<>();
    for(int i=0; i<order.length(); ++i){
      char ch = order.charAt(i);
      map.put(ch, i);
    }
    
    for(int i=0; i<words.length-1; ++i){
      if(!check(words[i], words[i+1], map)) return false;
    }
    return true;
  }
  
   boolean check(String w1, String w2, Map<Character, Integer> map){
    int n1 = w1.length(), n2 = w2.length();
    int i = 0;
    while(i<n1 && i<n2){
      int p1 = map.get(w1.charAt(i));
      int p2 = map.get(w2.charAt(i));
      if(p1!=p2) return p1<p2;
      i++;
    }
    
    return n1<=n2;
  }
}