My solution using HashMap


  • 0
    A
    public class Solution {
    	public String multiply(String num1, String num2) {
    	if (num1.compareTo("0")==0 || num2.compareTo("0")==0)
    	{
    	    return "0";
    	}
    	// position to all its numbers
    	HashMap<Integer, Integer> res = new HashMap<Integer, Integer>();
    	for (int i = 0; i < num1.length(); i++) {
    		for (int j = 0; j < num2.length(); j++) {
    			int l1 = num1.length() - i;
    			int l2 = num2.length() - j;
    			char c1 = num1.charAt(i);
    			char c2 = num2.charAt(j);
    			int tmp = ((int) c1 - 48) * ((int) c2 - 48);
    			int h = tmp / 10;
    			int hnum = l1 + l2;
    			int l = tmp % 10;
    			int lnum = l1 + l2 - 1;
    			if (h != 0) {
    				if (res.containsKey(hnum)) {
    					res.put(hnum, res.get(hnum)+h);
    				} else {
    					res.put(hnum, h);
    				}
    			}
    			if (res.containsKey(lnum)) {
    				res.put(lnum, res.get(lnum)+l);
    			} else {
    				res.put(lnum, l);
    			}
    		}
    	}
    	boolean exit = true;
    	do 
    	{	
    		exit = true;
    		ArrayList<Integer> keys = new ArrayList<Integer>();
    		keys.addAll(res.keySet());
    		for (Integer key : keys) {
    			int value = res.get(key);
    			if (value >= 10) {
    				int h = value / 10;
    				int l = value % 10;
    				if (res.containsKey(key + 1)) {
    					int xval = res.get(key + 1) + h;
    					if(xval >= 10)
    						exit = false;
    					res.put(key + 1, xval);
    				} else {
    					res.put(key + 1, h);
    				}
    				res.put(key, l);
    			}
    		}
    	}while(!exit);
    	int max = -1;
    	for (int key : res.keySet()) {
    		if (key > max) {
    			max = key;
    		}
    	}
    	String stres = "";
    	for (int i = 1; i <= max; i++) {
    		if (res.containsKey(i)) {
    			stres = res.get(i) + stres;
    		} else {
    			stres = "0" + stres;
    		}
    	}
    	return stres;
    }
    

    }


Log in to reply
 

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