43. Multiply Strings

Multiply Strings

Solution 1:
     The Length is way larger than 64 bit integer, which length is 19
    
     Python3.5: Integers have unlimited precision, in most situations of industrial work, just use the simplest and most readable way to do it.

     Intuitively, multiply digit by digit, and add sum up. Use a String to store temporary result and 'add' it into result.

    Example: 13*34=13*4+13*30
    Here 13 is num1, 14 is num2, need to multiply in reverse order

 def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'
    revret = '' # store the result in reverse order for easy computation
    zeros='' #this is used for add 0 for next inner iteration
    for d1 in reversed(num1):
        tmp = ''
        offset = 0
        for d2 in reversed(num2):
            sum = int(d2)*int(d1)+offset
            tmp += str(sum%10)
            offset = sum/10
        if offset:
            tmp += str(offset)
        revret = self.addNumInReverse(revret, zeros+tmp)
        zeros+='0'
    return revret[::-1]
def addNumInReverse(num, tmp):

    if len(num) < len(tmp):
        t = tmp
        tmp = num
        num = t

    re = ""
    off = 0
    
    for i, n in enumerate(num):
        sum = off + int(n) + (int(tmp[i]) if i < len(tmp) else 0)
        re+=str(sum%10)
        off = sum/10                     
    if off:
        re += str(off)         
    return re

Solution 2:
Don't have to add it up in when they first multiplied together.   

          
Use array to store each multiplied result, add it up at last.                      

Maximum product length = len(A) + len(B)

def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'

    retval = [0]*(len(num1)+len(num2))
    num1 = list(reversed(num1))
    num2 = list(reversed(num2))
    k=0

    for i, d1 in enumerate(num1):
        for j, d2 in enumerate(num2):                
            retval[j+k] += int(d1)*int(d2)
        k+=1
    ret = ""
    off = 0

    for i in xrange(len(retval)):
        sum = retval[i] + off
        ret = str(sum%10) + ret
        off = sum/10
    if off:
        ret = off + ret

The number of distinct substrings

reference 
https://www.quora.com/Given-a-string-how-do-I-find-the-number-of-distinct-substrings-of-the-string

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

分两步：
1.找到所有suffix
2.find number of distinct substrings  based on LCP（longest common prefix）

例子：BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

因此go through every suffixes的prefix就构成了所有substrings。也就是对以ith位置作为substring头构成的所有substrings。对于每个suffix而言，能构成以ith位置为头的substring的个数就是这个suffix的长度

因此我们需要算的就是这些suffix中的重复量。我们不需要算出重复量，我们可以跳过重复计算不重复部分的长度

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

LCP = Longest Common Prefix of 2 strings.

初始化
ans = length(first suffix) = length("A") = 1.

The consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,
LCP("A", "ANA") = "A".
因此对于"ANA"而言，能构成不和前面重复的prefix substring就是相当于suffix为NA

So we have, 

ans += length("ANA") - LCP("A", "ANA") 
ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

LCP("ANA", "ANANA") = "ANA".
ans += length("ANANA") - length(LCP)
=> ans = ans + 5 - 3
=> ans = 3 + 2 = 5.

3. Longest Substring Without Repeating Characters

1. 题意

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

2.算法

hashMap<Character,indexOfCharacter>

当找到重复的时候记录non-duplicate substring的起始位置 map.get(c)+1
或者用一个array当作map

   public int lengthOfLongestSubstring(String s) {  
     int[] visited = new int[128];  
     Arrays.fill(visited,-1);  
     int max = 0, begin = 0;  
     for(int i = 0; i <s.length(); i++){  
       char c = s.charAt(i);  
       if(visited[c]==-1||begin > visited[c]){  
         visited[c] = i;  
       }else{  
         max = Math.max(max, i-begin);  
         begin = visited[c]+1;  
         visited[c] = i;  
       }  
     }  
     max = Math.max(max,s.length()-begin);  
     return max;  
   }  

Acme substring

1. 题意：在string A里边找X *是wildcard character 可以match any character
返回the starting position

2.算法：
test case:
a is shorter then x

KMP

  lps[i] = the longest proper prefix of pat[0..i] 
              which is also a suffix of pat[0..i]. 

Examples:
For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Searching Algorithm:
Unlike the Naive algo where we slide the pattern by one, we use a value from lps[] to decide the next sliding position. Let us see how we do that. When we compare pat[j] with txt[i] and see a mismatch, we know that characters pat[0..j-1] match with txt[i-j+1…i-1], and we also know that lps[j-1] characters of pat[0…j-1] are both proper prefix and suffix which means we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will anyway match.

Preprocessing Algorithm:
In the preprocessing part, we calculate values in lps[]. To do that, we keep track of the length of the longest prefix suffix value (we use len variable for this purpose) for the previous index. We initialize lps[0] and len as 0. If pat[len] and pat[i] match, we increment len by 1 and assign the incremented value to lps[i]. If pat[i] and pat[len] do not match and len is not 0, we update len to lps[len-1]. 

 public static int firstOccurrence(String a, String x){  
        int[] lps = longestPrefixSuffix(x);  
        System.out.println(Arrays.toString(lps));  
        int i = 0, j= 0;  
        while(i < a.length()){  
             System.out.println(j);  
             if(j == x.length()){  
                  return i - x.length();  
             }  
             if(a.charAt(i) == x.charAt(j) || x.charAt(j) == '*'){  
                  i++;j++;  
             }else{  
                  if(j==0)  
                       i++;  
                  else  
                       j = lps[j-1];  
             }  
        }  
        return j == x.length()? i-x.length():-1;  
      }  
      public static int[] longestPrefixSuffix(String s){  
           int len = 0;  
           int i = 1;  
           int[] lps = new int[s.length()];  
           while(i<s.length()){  
                if(s.charAt(i) == s.charAt(len) ){  
                     len++;  
                     lps[i] = len;  
                     i++;  
                }else{  
                     if(len == 0){  
                          lps[i] = len;  
                          i++;  
                     }   
                     else{  
                          len = lps[len-1];  
                     }  
                }  
           }  
           return lps;  
      }