Number of Atoms


  • 0

    Click here to see the full article post


  • 0
    J

    Approach #2: Stack [Accepted] has a bug.
    line 13 should be int iStart = ++i, count = 1;
    line 15 should be int multiplicity = i > iStart ? Integer.parseInt(formula.substring(iStart, i)) : 1;


  • 0

    @jul599 Thanks, corrected


  • 0

  • 0
    R

    It's an interesting problem, but I don't think we have O(N) solution here.

    All the solutions described above are O(N^2) and not O(N). In all of them we need to merge a internal formula into surrounding one, and thus if we have an input where the number of atoms is equal to number of nested formulas -
    like A(B(C(D(E(F(G)2)2)2)2)2)2, then on every step the number of atoms to merge will increment - like 1, 2, 3, 4.. and therefore the total time is quadratic.

    Here's the code that generate 1m input and apparently doesn't complete in a reasonable time:

    T = ('a','b','c', 'd', 'e', 'f', 'g')
    S = ""

    for c1 in T:
    for c2 in T:
    for c3 in T:
    for c4 in T:
    for c5 in T:
    for c6 in T:
    for c7 in T:
    S += c1.upper() + c2 + c3 + c4 + c5 + c6 + c7 + "("

    S += "H20"
    for i in range(0, len(T) ** len(T)):
    S += ")2"

    print("Number of atoms: " + str(len(S) / 10))

    R = Solution().countOfAtoms(S)

    print("Done: " + str(len(R)))
    print("Result: " + R)


  • 0

    @rassokhin Thanks. I corrected the article.


  • 0
    B

    Is not it O(N) solution complexity. Sketch: going in backwards order, e.g. get )3 push 3 to stack, multiplier = 3, get )2, push 2 to stack, multiplier: 3 * 2 = 6,
    get O, use current multiplier O6, get (, pop 2 from stack, multiplier = 6 / 2 = 3
    And so on. So O(N).


  • 0
    D

    I don't think O(N^2) is a tight upper bound. The tighter bound would be O(BN) since each token will be looked at at most O(B) times, where B is the number of bracketed expressions.

    For example,

    1. A(B(C(D(E(F3)4)5)6)7) --> Here, B = O(N), so O(N^2)
    2. A(B(CDEFGHIJ)3)2 --> Here, N >> B, and we parse, each element O(B) times, so O(BN)

  • 0

    Really great solutions! The following is the "missing" regular expression solution in Java :-)

    import java.util.regex.*;
    
    class Solution {
        public String countOfAtoms(String formula) {
            final Stack<Map<String, Integer>> stack = new Stack<>();
            stack.push(new TreeMap<>());
            final Pattern pattern = Pattern.compile("([A-Z][a-z]*)(\\d*)|(\\()|(\\))(\\d*)");
            final Matcher matcher = pattern.matcher(formula);
            while (matcher.find()) {
                final String match = matcher.group();
                if (match.equals("(")) {
                    stack.push(new TreeMap<>());
                } else if (match.startsWith(")")) {
                    final Map<String, Integer> top = stack.pop();
                    final int multiple = match.length() > 1 ? Integer.parseInt(match.substring(1, match.length())) : 1;
                    for (final String name : top.keySet()) {
                        stack.peek().put(name, stack.peek().getOrDefault(name, 0) + top.get(name) * multiple);
                    }
                } else {
                    int i = 1;
                    while (i < match.length() && Character.isLowerCase(match.charAt(i))) {
                        i++;
                    }
                    final String name = match.substring(0, i);
                    final int count = i < match.length() ? Integer.parseInt(match.substring(i, match.length())) : 1;
                    stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count);
                }
            }
            final StringBuilder sb = new StringBuilder();
            for (final String name : stack.peek().keySet()) {
                sb.append(name);
                final int count = stack.peek().get(name);
                if (count > 1) {
                    sb.append(String.valueOf(count));
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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