# 20191222

#### 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

#### Nick

 public String longestCommonPrefix(String[] strs) {
     if (strs == null || strs.length == 0) return "";
     String prefix = strs[0];
     for (int i = 1; i < strs.length; i++) {
         while(nums[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
         }
     }
     return prefix;
 }

#### Ian

n * m
function longestCommonPrefix(strs) {
  let index = 0;
  let prefix = '';
  if(strs.lenght < 1) return '';
  while(strs[0][index] !== undefined) {
      let count = 1;
      for(let i = 1; i < strs.length; i++) {
            if(strs[i][index] === strs[0][index]) {
                count ++;
            }
      }
      if(count === strs.length) {
          prefix += strs[i][index];
      }
      index ++;
  }
  return prefix;
 }

#### 516. Longest Palindromic Subsequence

Medium

Share
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
 
 012345
 aabbaa <-> 6
 aaabba <-> 6
 aaaabb
 baaaab
 bbaaaa
 abbaaa
 
 bbbab
 bbbba
 abbbb
 babbb
 
 
 
 01234
 aabaa <-> 5
 
 ...bbbabbbbabbbbabbbbabbbbabbbbabbbbabbbbabbbbab...
 
 
 01234
 bbbab ((0, 4) (1, 2))
 2 + 2 = 4
 
 0123
 cbbd
 2 (1, 2)

Example 1:
Input: "bbbab"
Output: 4

bbb
bbbb
bab
bb

Example 2:
Input: "cbbd"
Output: 2

@lakecarrot
Check the link here.
I think the problem should state that find a substring which "contains" the longest palindromic sequence.
For example:
Given "abxyzbahj",
"abxba", "abyba" and "abzba" are the longest palindromic sequence which is in the substring "abxyzba".
Therefore, the returning answer should be the length of "abxba" which is 5.

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        return lps(s, 0, s.length()-1, dp);
    }
    private int lps(String s, int i, int j, int[][] dp){
        if(i > j)
            return 0;
        if(dp[i][j] != 0)
            return dp[i][j];
        if(i == j)
            dp[i][j] = 1;
        else if(s.charAt(i) == s.charAt(j))
            dp[i][j] =  2+lps(s, i+1, j-1, dp);
        else
            dp[i][j] = Math.max(lps(s, i+1, j, dp), lps(s, i, j-1, dp));
        return dp[i][j];
    }
}

#### 26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.

Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

 public int removeDuplicates(int[] nums) {
     if (nums == null || nums.length == 0) return 0;
     int duplicates = 0;
     for (int i = 1; i < nums.length; i++) {
         if (nums[i] == nums[i - 1]) {
            duplicates++;
         }
         nums[i - duplicates] = nums[i];
     }
     
    return nums.legnth - duplicates;
 }