Multiply Strings, Implement strStr(), Reverse Words in a String, String to Integer (atoi)

Multiply Strings

Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

First Solution

reverse two input strings, so index and digits are the same

create a tmp int[] to store the additions of two digits multiply results

add up the array, while inserting into a stringbuilder

delete zeros in the beginning

 
 public String multiply(String num1, String num2) {
 num1=new StringBuilder(num1).reverse().toString();
 num2=new StringBuilder(num2).reverse().toString();
 int[] tmp= new int[num1.length()+num2.length()];
 StringBuilder res=new StringBuilder();
 for(int i = 0; i< num1.length();i++){
   for(int j = 0; j<num2.length();j++){
     tmp[i+j]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
   }
 }
 
 for(int i=0;i<tmp.length;i++){
   int carries=0, num=0;
   num=tmp[i]%10;
   carries=tmp[i]/10;
   res.insert(0, num);
   if(i!=tmp.length-1){tmp[i+1]+=carries;}
 }
 
 while(res.length()>1&&res.charAt(0)=='0'){res.deleteCharAt(0);}
 return res.toString();
}

Second Solution

Do it reversly, same process:

  
  public String multiply(String num1, String num2) {
  int[] tmp= new int[num1.length()+num2.length()];
  StringBuilder res=new StringBuilder();
  int j=0,i,num,carries=0;
  for( i = num1.length()-1; i>=0 ;i--){
      carries=0; num=0;
    for( j = num2.length()-1; j>=0;j--){        
      num=(num1.charAt(i)-'0')*(num2.charAt(j)-'0')+tmp[i+j+1]+carries;
      tmp[i+j+1]=num%10;
      carries=num/10;
    }
    tmp[i+j+1]=carries;
  }
  i=0;
  while(i<tmp.length-1&&tmp[i]==0){i++;}
  while(i<tmp.length){res.append(tmp[i++]);}
  return res.toString();
}

---

Implement strStr()

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

Naive Solution

Two pointers:

i: from 0 to n-m, check each substring(i,i+m) equals to needle

j: from i to m+i-1, break if non-equal character found

If j=m+i after some round, then we found a substring(i, i+m) matches the needle.

public int strStr(String haystack, String needle) 
  {  
    int n = haystack.length();  
    int m = needle.length(); 
    //if haystack empty but needle not
    if (n==0 && m!=0) return -1;
    //special case 
    else if(n==0||m==0) return 0;
    else{
      for (int i = 0; i < n - m+1; i++)  
      {   int j=i;
        for (; j < m+i; j++)  
        {  
          if (needle.charAt(j-i) != haystack.charAt(j)) break;  
        }  
        if (j == m+i) return  i;
      }  
      return -1;  }
  }

More Consice:

public int strStr(String haystack, String needle) {
       if(haystack == null || needle == null) {
           return 0;
       }
       int i, j;
       for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
           for(j = 0; j < needle.length(); j++) {
               if(haystack.charAt(i + j) != needle.charAt(j)) {
                   break;
               }
           }
           if(j == needle.length()) {
               return i;
           }
       }
       return -1;
   }

KMP is another solution.

---

Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.
Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

Correct Solution:

First, split words into array by spaces. Then from last element in array, append to stringBuilder if not space, add one space after that element in the new string. At last, get the substring from 0 to sb.length()-1 to delete the ending space.

public String reverseWords(String s) {
  if(s==null||s.length()==0) return "";
  String[] words=s.split(" ");
  int n=words.length;
  StringBuilder sb=new StringBuilder();
  for(int i=n-1; i>=0;i--){
    if(!words[i].equals("")){
      sb.append(words[i]).append(" ");}
  } return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
}

---

String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Naive Sulotion

Case 1: general case, given string is a valid input, convert to int directly

Case 2: input string is null or all blank, return 0;

Case 3: sign of number(+/-, default as +)

Case 4: overflow

public int atoi(String str){
    if(str==null) return 0;
    //remove spaces at beginning and end
    str=str.trim();
    int n=str.length(),i=0;
    //use long to store result
    long res=0;
    if(n==0) return 0;
    int sign = 1;
    if(str.charAt(i)=='+') {sign=1;i++;}
    else if(str.charAt(i)=='-') {sign=-1;i++;}
    for(;i<n;i++){
      char tmp=str.charAt(i);
      if(tmp>'9'||tmp<'0'||tmp==' ') break;
      res=res*10+(tmp-'0');
      if(res>Integer.MAX_VALUE) return sign==1 ? Integer.MAX_VALUE: Integer.MIN_VALUE;
    }
    return (int)res*sign;
  }

An alternative solution

without using long, is to use the following during loop:

Integer.MAX_VALUE/10 < res;

res*10 will become bigger than MAX

Integer.MAX_VALUE/10 == res && Integer.MAX_VALUE%10 <(str.charAt(i) - ‘0’)

compare last digit when res*10=MAX

public int atoi(String str){
    if(str==null) return 0;
    str=str.trim();
    int n=str.length(),i=0;
    int res=0;
    if(n==0) return 0;
    int sign = 1;
    if(str.charAt(i)=='+') {sign=1;i++;}
    else if(str.charAt(i)=='-') {sign=-1;i++;}
    for(;i<n;i++){
      char tmp=str.charAt(i);
      if(tmp>'9'||tmp<'0'||tmp==' ') break;
      if(Integer.MAX_VALUE/10 < res || (Integer.MAX_VALUE/10 == res && Integer.MAX_VALUE%10 <(str.charAt(i) - '0')))
      return sign==1 ? Integer.MAX_VALUE: Integer.MIN_VALUE;    
      res=res*10+(tmp-'0');
    }
    return (int)res*sign;
  }