3
\$\begingroup\$

I have a string that contains a random order of parenthesis {[()]}. I want to check if for any given parenthesis is there a matching closing one.

Example:

 }}}{{{ //true
 {[]    //false
 {[()]} //true
private static bool checkIfWellFormatted(string inputString)
{

    if (string.IsNullOrEmpty(inputString))
        throw new ArgumentException("String is empty");
    if ((inputString.Length % 2) != 0)
        return false;

    Dictionary<char, int> _inputDictionary = new Dictionary<char, int>();

    foreach (Char c in inputString)
    {
        if (!_inputDictionary.ContainsKey(c))
            _inputDictionary.Add(c, 0);
        else
            _inputDictionary[c] += 1;

    }

    foreach (var item in _inputDictionary)
    {
        char oppKey = '\0';
        if (item.Key == '{')
            oppKey = '}';
        if (item.Key == '}')
            oppKey = '{';

        if (item.Key == '(')
            oppKey = ')';
        if (item.Key == ')')
            oppKey = '(';

        if (item.Key == '[')
            oppKey = ']';
        if (item.Key == ']')
            oppKey = '[';

        if (_inputDictionary.ContainsKey(oppKey))
        {
            var value = _inputDictionary[oppKey];
            if (value != item.Value)
                return false;

        }
        else
            return false;


    }

    return true;
}

Here, the second iteration over the dictionary has \$O(n)\$ complexity. Can I improve its time complexity?

\$\endgroup\$
  • \$\begingroup\$ A better definition of the problem would help here. If all you need is to count opening and closing marks and make sure the numbers match, that's less involved than caring whether they overlap and suchlike. \$\endgroup\$ – cHao Feb 10 '17 at 17:00
  • \$\begingroup\$ [({])} is this a valid combination? \$\endgroup\$ – t3chb0t Feb 10 '17 at 18:35
  • 1
    \$\begingroup\$ @t3chb0t I'd say yes, as long as all present parentheses have they're opening/closing partner in the string it's fine. \$\endgroup\$ – Denis Feb 10 '17 at 19:01
  • \$\begingroup\$ @Denis mhmm, but the examples show only properly nested ones so this is not so obvious. \$\endgroup\$ – t3chb0t Feb 10 '17 at 19:07
  • \$\begingroup\$ Can the string contain non parentheses characters? \$\endgroup\$ – Denis Feb 10 '17 at 19:32
2
\$\begingroup\$

One thing you can do is insert beforehand the characters you want to track.

    var _inputDictionary = new Dictionary<char, int>();

    foreach (char c in "{}[]()")
    {
        _inputDictionary.Add(c, 0);
    }

At that point, you can avoid counting every char, and just count the ones you care about.

    foreach (char c in inputString)
    {
        if (_inputDictionary.ContainsKey(c)) _inputDictionary[c] += 1;
    }

And when you're done, rather than having potentially thousands of chars (because you don't restrict input), _inputDictionary always only contains exactly the (currently 6) chars you care about.

Now, as for checking those, since you already know what keys you have and don't have to be paranoid about nulls and such, you can simplify it down to something like

    return _inputDictionary['{'] == _inputDictionary['}']
        && _inputDictionary['('] == _inputDictionary[')']
        && _inputDictionary['['] == _inputDictionary[']']
    ;

All together:

private static bool checkIfWellFormatted(string inputString)
{
    // Just so it's said, by the definition you've given in the question,
    // "" is vacuously well-formatted. (There is a matching delimiter for
    // every one of the 0 chars in the string.) I'd suggest only throwing
    // on null and letting "" be checked (or just return true, considering
    // you already know the result).
    if (string.IsNullOrEmpty(inputString))
        throw new ArgumentException("String is empty");

    // This can speed up the comparison, but only if you outlaw any other
    // characters in the string. Since you don't do that in any way, it
    // simply leads to incorrect answers.
    // if ((inputString.Length % 2) != 0)
    //     return false;

    Dictionary<char, int> _inputDictionary = new Dictionary<char, int>();

    foreach (char c in "{}[]()")
    {
        _inputDictionary.Add(c, 0);
    }

    foreach (char c in inputString)
    {
        if (_inputDictionary.ContainsKey(c)) _inputDictionary[c] += 1;
    }

    return _inputDictionary['{'] == _inputDictionary['}']
        && _inputDictionary['('] == _inputDictionary[')']
        && _inputDictionary['['] == _inputDictionary[']']
    ;
}
\$\endgroup\$
  • \$\begingroup\$ I was thinkin in second iteration we can use dictionary.ElementAt() method but then since we are iterating over dictionary the complexity will be still O(n).The thing here is I am trying to make a new problem statement by modifying balancing paranthesis algo stackoverflow.com/questions/2711032/… I am just trying to come with something new \$\endgroup\$ – Rohit Feb 10 '17 at 17:13
  • \$\begingroup\$ Balanced parens is a whole different thing than what you seem to be trying to do. Especially with three different types of delimiters, you'll need a stack in order to do it decently. \$\endgroup\$ – cHao Feb 10 '17 at 17:17
  • 1
    \$\begingroup\$ When you're tallying every character, O(n) can matter. But it isn't really an issue here when you know n=6. Once that's defined, it's no longer O(n) -- it's more like O(6). it does the same amount of work no matter how many chars you've tallied. \$\endgroup\$ – cHao Feb 10 '17 at 17:19
9
\$\begingroup\$

You could evict the count dictionary altogether and use three counters. Next, you scan each character and increment/decrement the corresponding counter. The answer is true if after scanning all the characters all three counters are zero. For example, if we scan [, we increment the counter for [ and ]; if we scan ], we decrement that very same counter. (Before the scan all counters are set to zero.)

All in all, I had this in mind:

private static bool WellFormatted(string inputString)
{
    int braceCount = 0;         // Counts '{' and '}'.
    int parenthesisCount = 0;   // Counts '(' and ')'.
    int squareBracketCount = 0; // Counts '[' and ']'.

    foreach (char c in inputString)
    {
        switch (c)
        {
            case '{':
                braceCount++;
                break;

            case '}':
                braceCount--;
                break;

            case '(':
                parenthesisCount++;
                break;

            case ')':
                parenthesisCount--;
                break;

            case '[':
                squareBracketCount++;
                break;

            case ']':
                squareBracketCount--;
                break;
        }
    }

    return braceCount == 0
        && parenthesisCount == 0
        && squareBracketCount == 0;
}

Also, from mathematical perspective, I would accept the empty string as a valid "parenthezation."

\$\endgroup\$
  • \$\begingroup\$ This solution is about 6x faster then the accepted one. \$\endgroup\$ – t3chb0t Feb 11 '17 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.