Java, List + Map


  • 0
    class Solution {
        public String countOfAtoms(String formula) {
            List<String> ls = new ArrayList<String>();
            Map<String, Integer> map = new HashMap<String, Integer>();
            int len = formula.length(), bNum = 1, i = 0;
            while (i < len) {
                if (formula.charAt(i) == '(') {
                    int currentBNum = getCurrentBNum(formula, i);
                    bNum *= currentBNum;
                    i++;
                } else if (formula.charAt(i) == ')') {
                    int currentBNumStartI = i + 1, j = currentBNumStartI;
                    while (j < len && Character.isDigit(formula.charAt(j))) j++;
                    String currentBNumS = formula.substring(currentBNumStartI, j);
                    int currentBNum = Integer.parseInt(currentBNumS);
                    bNum /= currentBNum;
                    i++;
                } else {
                    int j = i, iStartOfAtom = j;
                    if (j < len && Character.isUpperCase(formula.charAt(j))) j++;
                    if (j < len && Character.isLowerCase(formula.charAt(j))) j++;
                    
                    if (iStartOfAtom < j) {
                        String atom = formula.substring(iStartOfAtom, j);
    
                        int iStartOfCnt = j;
                        while (j < len && Character.isDigit(formula.charAt(j))) j++;
                        String cntS = formula.substring(iStartOfCnt, j);
                        int cnt = cntS.equals("") ? 1 : Integer.parseInt(cntS);
                        cnt *= bNum;
    
                        if (ls.contains(atom) && map.containsKey(atom)) map.put(atom, map.get(atom) + cnt);
                        else {
                            ls.add(atom);
                            map.put(atom, cnt);
                        }
                        
                    }
                    if (i == j) i++;
                    else i = j;
                }
                
            }
            
            return fToString(formula, ls, map);
        }
        
        private static int getCurrentBNum(String formula, int lBI) {
            int len = formula.length(), lBCnt = 0, rBI = -1;
            for (int i = lBI; i < len; i++) {
                if (formula.charAt(i) == '(') lBCnt++;
                else if (formula.charAt(i) == ')') lBCnt--;
                if (lBCnt == 0) {
                    rBI = i;
                    break;
                }
            }
            int bNumStartI = rBI + 1, i = bNumStartI;
            while (i < len && Character.isDigit(formula.charAt(i))) i++;
            String bNumS = formula.substring(bNumStartI, i);
            int bNum = Integer.parseInt(bNumS);
            
            return bNum;
        }
        
        private static String fToString(String fml, List<String> ls, Map<String, Integer> map) {
            Collections.sort(ls);
            StringBuilder sb = new StringBuilder();
            Iterator<String> it = ls.iterator();
            while (it.hasNext()) {
            	String atomS = it.next();
            	sb.append(atomS);
                int cnt = map.get(atomS);
                if (cnt > 1) sb.append(cnt);
            }
            return sb.toString();
        }
    }
    

    ls: store the atom strings
    map: store the atom to cnt
    bNum: namely bracket number, which is the number right after the current right bracket, everytime the number of an atom inside a bracket should be multiplied by bNum.


Log in to reply
 

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