Showing posts with label String. Show all posts
Showing posts with label String. Show all posts

Saturday, December 16, 2017

Leetcode - 214. Shortest Palindrome

214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

Analysis:
  S#S' will make a valid palindrome. Key is to use KMP algo to find existing repeating part from the half, which is S
 ex1:   aa#aa
KMP: 01012  -> so we will have s.substring(2).reverse + s = '' + 'aa' = 'aa'
ex2:   bba#abb
KMP: 0100012 -> so we will have s.substring(1).reverse +  s = 'a.reverse' + 'bba' = abba

Complexity: O(N)


var shortestPalindrome = function(s) {
    if(s.length < 1){return s;}
    var pali = s+"#"+s.split("").reverse().join("");//s#s'
   //storing next entry pos for comparision
    var kmp = getKMP(pali);
    console.log(kmp)
    var length = kmp[kmp.length-1];
    return s.substring(length).split("").reverse().join("") + s;
};

function getKMP(s){
    var j = 0;
    var table = [];
    table[0] = 0;
    for(var i = 1; i < s.length; i++){
        while(s[i] !== s[j] && j > 0){
            j = table[j-1];
        }
        if(s[i] === s[j]){
            table[i] = j+1;
            j++;
        }else{
            table[i] = 0;
        }
    }
    return table;
}

Monday, April 17, 2017

Leetcode -- 5. Longest Palindromic Substring(Strategy)

5. Longest Palindromic Substring
medium
https://leetcode.com/problems/longest-palindromic-substring/#/description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
Example:
Input: "cbbd"

Output: "bb"
思路: - iterate string, keep finding longer palindrome(curLen)
                  check if str[i-curlen-1, i]: curLen+=2
                  else if str[i-curlen, i]: curLen+=1

Complexity: Time O(n^2) for "aaaa..a" Space O(1)

public String longestPalindrome(String s) {
        //if ...*axxa (a), we check if *axxaa isPalindrome
        // else axxa(a)
        //else palindrome disconnect here
        //keep tracking current len to set begin, cuz if < current len, not longest, skip
        if(s.length() < 2)return s;
        String res = "";
        int curLen = 0;//watch index boundary
        for(int i = 1; i < s.length(); i++){
            if(isPalindrome(s, i-curLen-1, i)){
                res = s.substring(i-curLen-1, i+1);//susbstring
                curLen += 2; 
            }else if(isPalindrome(s, i-curLen, i)){
                res = s.substring(i-curLen,i+1);
                curLen += 1;
            }
        }
        return res;
    }
    public boolean isPalindrome(String s, int begin, int end){
        if(begin < 0)return false;
        while(begin < end){
            if(s.charAt(begin) == s.charAt(end)){
                begin++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }

Monday, January 23, 2017

Leetcode/各大家 -- 13. Roman to Integer (Math)

13. Roman to Integer (Math, str)
easy
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

思路: 倒着走array, 如果 cur >= post (eg: XI), res += cur val,
                                   else  cur < post (eg: IX) res -= cur val


public class Solution {
    public int romanToInt(String s) {
        int res = 0;
        int len = s.length();
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        res = map.get(s.charAt(len - 1));
        for(int i = len - 2; i >= 0; i--){//eg: XI = 11, IX = 9
            int cur = map.get(s.charAt(i));
            int post = map.get(s.charAt(i + 1));
            if(cur >= post){
                res += cur;
            }else{
                res -= cur;
            }
        }
        return res;
    }
}

Wednesday, January 18, 2017

Leetcode/F家微软 -- 273. Integer to English Words (Recursion)

273. Integer to English Words (Recursion)
Hard
https://leetcode.com/problems/integer-to-english-words/
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

思路: recursively find answer, but mostly tricks. (545 % 100 = 45)
* Use 1000 to separate number parts. * put empty string in array for easy indexing
* Process number by dividing 1000, and helper handles from (0-999), 注意整数,word从小(右)加起, eg 5,357,545 is five million three hundred fifty seven thousand five hundred forty five
* use trim() to remove extra spaces in the end (trim can also remove start, not used here)

public class Solution {
    //"" is kept for index simplicity. TENS: 1st 2nd never used, keep for index simplicity
    private final String[] LESS_THAN_20 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven",
"Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    private final String[] TENS = {"","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
    private final String[] THOUSANDS = {"","Thousand","Million","Billion"};
    public String numberToWords(int num) {
        if(num == 0)return "Zero";
        int i = 0;//ptr to thousands
        String words = "";
        while(num>0){
            if(num%1000 != 0){//avoid special case 1,000,000 else return one million thousand
                words = helper(num%1000) + THOUSANDS[i] + " " + words;
            }
            num /= 1000;
            i++;
        }
        return words.trim();//remove extra space in the end.
    }
    private String helper(int num) {
        if( num == 0){
            return "";
        }else if(num < 20){
            return LESS_THAN_20[num] + " ";
        }else if(num < 100){
            return TENS[num/10] + " " + helper(num%10);//avid extra space by recur call
        }else{//100-999
            return LESS_THAN_20[num/100] + " Hundred " + helper(num%100);
        }
    }
}
 步骤:

Monday, January 16, 2017

Leetcode/G家 344.345. Reverse Vowels of a String (2pointer)

345. Reverse Vowels of a String(2pointer)
easy
https://leetcode.com/problems/reverse-vowels-of-a-string/
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
思路: convert to char array, use two pointer: i - track the vowel from begin; j - track the vowel from end
          once both i & j point to vowel, swap char

public class Solution {
    public String reverseVowels(String s) {
        char[] word = s.toCharArray();
        Set<Character> set = new HashSet<Character>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        int i = 0,j = word.length-1;
        while(i<j){
            char a = word[i];
            char b = word[j];
            if(!set.contains(a)){
                i++;
            }else if(!set.contains(b)){
                j--;
            }else{//a & b both vowel
                word[i] = b;
                word[j] = a;
                i++;
                j--;
            }
        }
        return new String(word);
    }
}

304, simply reverse string

思路: use two pointer i from start, j from end, keep swaping i++, j-- while i < j
public class Solution {
    public String reverseString(String s) {
        char[] word = s.toCharArray();
        int i = 0,j = word.length-1;
        while(i<j){
            char tmp = word[i];
            word[i] = word[j];
            word[j] = tmp;
            i++;
            j--;
        }
        return new String(word);
    }
}

Saturday, January 7, 2017

Leetcode -- 434. Number of Segments in a String

434. Number of Segments in a String
  • Difficulty: Easy
https://leetcode.com/problems/number-of-segments-in-a-string/

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
思路: watch 1st char + count segments start with ' ' 

public class Solution {
    public int countSegments(String s) {
        if(s.length()<1) return 0;
        int count = 0;
        if(s.charAt(0)!=' ') count++;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i-1)==' '&&s.charAt(i)!=' ')count++;
        }
        return count;
    }
}

Friday, January 6, 2017

Leetcode/F家--43. Multiply Strings(Math)

43. Multiply Strings(Math)
Medium 
https://leetcode.com/problems/multiply-strings/

 Company: F家,twitter
思路:  conclude that
 `num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]` //1st pos: inc, 2nd: sum + mul
using int[] to add up results in double for loop.O(mn)



public class Solution {
    public String multiply(String num1, String num2) {       
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                int mul = (num1.charAt(i) - '0')*(num2.charAt(j) - '0');
                int p1 =i+j,p2=i+j+1;
                int sum = pos[p2]+mul;
                pos[p1] += sum/10;
                pos[p2] = sum%10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m+n;i++){ 
            if(!(sb.length() == 0 && pos[i] == 0)) sb.append(pos[i]);//avoid "00"
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}