AC Java O(mn) Primary School Solution.


  • 1
    D

    Three Functions:

    1. multiplyChar(string, char, numOfZeros):return the product of string1 and a char in string2, add zeros according to the position of
      the char in string2.

    2. addTwoNumbers(lastResult, newResult): accumulate the products of string1 * each char in string2.

    3. main function: return result.

    public class Solution {
        public String addTwoString(String s1,String s2)
        {
            if(s1.length()==0||s1.equals("0"))
                return s2;
            if(s2.length()==0||s2.equals("0"))
                return s1;
            int carry=0;
            int maxLength=Math.max(s1.length(),s2.length());
            StringBuilder builder=new StringBuilder();
            for(int i=0;i<maxLength;i++)
            {
                int s1Index=s1.length()-1-i;
                int s2Index=s2.length()-1-i;
                int s1Value=0;
                int s2Value=0;
                if(s1Index>=0)
                    s1Value=s1.charAt(s1Index)-'0';
                if(s2Index>=0)
                    s2Value=s2.charAt(s2Index)-'0';
                int curValue=s1Value+s2Value+carry;
                if(curValue>=10)
                {
                    curValue=curValue-10;
                    carry=1;
                }
                else
                    carry=0;
                builder.insert(0,curValue);
            }
            if(carry==1)
                builder.insert(0,1);
            while(builder.indexOf("0")==0&&builder.indexOf("0")!=builder.length()-1)
                builder.deleteCharAt(0);
            return builder.toString();
        }
        public String multiplyChar(String s,char c,int numOfZeros)
        {
            StringBuilder builder=new StringBuilder();
            if(c=='0')
                builder.append(0);
            else if(c=='1')
                builder.append(s);
            else
            {
                int carry=0;
                int cValue=c-'0';
                for(int i=s.length()-1;i>=0;i--)
                {
                    int curValue=(s.charAt(i)-'0')*cValue+carry;
                    carry=curValue/10;
                    curValue=curValue%10;
                    builder.insert(0,curValue);    
                }
                if(carry>0)
                    builder.insert(0,carry);
            }
            for(int i=0;i<numOfZeros;i++)
                builder.append(0);
            while(builder.indexOf("0")==0&&builder.indexOf("0")!=builder.length()-1)
                builder.deleteCharAt(0);
            return builder.toString();
        }
        public String multiply(String num1, String num2) {
            String result="0";
            for(int i=num2.length()-1;i>=0;i--)
            {
                result=addTwoString(result,multiplyChar(num1,num2.charAt(i),num2.length()-1-i));
            }
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.