apply stack and map to solve this problem


  • 0
    T
    class Solution {
        class chemical{
            String c;
            int count;
            chemical(String c,int count){
                this.c = c;
                this.count = count;
            }
        }
        
        public String countOfAtoms(String formula) {
             Deque<Map<String,Integer>> deque = new ArrayDeque<>();
             
             char[] array = formula.toCharArray();
             Map<String,Integer> map = new HashMap<>();
             String pre = "";
             for(int i = 0;i<array.length;i++){
                 char c = array[i];
                 if(Character.isDigit(c)){
                     int num = c-'0';
                     int j = i;
                     while(j+1<array.length && Character.isDigit(array[j+1])){
                         num = num*10 + array[j+1]-'0';
                         j++;
                     }
                     i=j;
                     if(!pre.equals(")")){
                         map.put(pre,map.getOrDefault(pre,0)+num-1);
                     }else{
                         Map<String,Integer> pre_map = deque.pollLast();
                         for(String key:map.keySet()){
                             pre_map.put(key,pre_map.getOrDefault(key,0)+map.get(key)*num);
                         }
                         
                         map = pre_map;
                     }
                 }else if(c=='('){
                     Map<String,Integer> copymap = new HashMap<>(map); 
                     deque.offer(copymap);
                     map = new HashMap<>();
                 }else if(c!=')'){
                     String str = c+"";
                     int j = i;
                     while(j+1<array.length&&array[j+1]>='a'&&array[j+1]<='z'){
                         j++;
                         str+=array[j];
                     }
                     i=j;
                     map.put(str,map.getOrDefault(str,0)+1);
                     pre = str;
                 }else{
                     pre=")";
                 }
             }
             
             StringBuilder sb = new StringBuilder();
             PriorityQueue<chemical> pq = new PriorityQueue<chemical>(1,new Comparator<chemical>(){
                    public int compare(chemical a,chemical b){
                        return (a.c).compareTo(b.c);
                    } 
             });
            
            for(String key:map.keySet()){
                pq.offer(new chemical(key,map.get(key)));
            }
            
            while(pq.size()!=0){
                chemical popNode = pq.poll();
                if(popNode.count!=1){
                   sb.append(popNode.c+popNode.count);
                }else{
                    sb.append(popNode.c);
                }
            }
            
            return sb.toString();
             
        }
    }
    

Log in to reply
 

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