# Non-stack java solution

• i implemented a divide and conquer solution without a stack, was wondering if anyone knows how it compares with solutions that use a stack (runtime, space, etc)

``````public class Solution {
public boolean isValid(String s) {
// return false if null
if (s == null) return false;

// return true if empty
if (s.equals("")) return true;

// %2 == 1 is a guaranteed mismatch
if (s.length() % 2 == 1) return false;

// first bracket
String first = s.substring(0, 1);

// non-open means mismatch
if ("([{".indexOf(first) == -1) return false;

// find the index of it's match
int index = matchIndexOf(first, s);

if (index == -1) return false;

// if match not at end of s
if (index != s.length())
{
// divide and conquer
return isValid(strip(s.substring(0, index))) && isValid(s.substring(index));
}
// otherwise, strip the brackets and try again
else
{
return isValid(strip(s));
}
}

// find matching paren
public int matchIndexOf(String first, String s)
{
String match;
// get the matching bracket
// s is guarenteed to be an open bracket
switch(first)
{
case "(":
match = ")";
break;
case "[":
match = "]";
break;
default:
match = "}";
}

// how "deep" we are
int level = 1;

// index we're checking
int index = 1;

// while we haven't found the match
while (level != 0)
{
// if we've hit the end of the string, we didn't find a match
if (index == s.length()) return -1;

// if we find another first, we go to next depth
if (s.substring(index, index + 1).equals(first)) level += 1;

// if we find a match, we come up a depth
else if (s.substring(index, index + 1).equals(match)) level -= 1;

// increment index
index += 1;
}

// if we make it this far, we've found our match
// return its index
return index;
}

// strip off end brackets
public String strip(String str)
{
return str.substring(0, str.length() - 1).substring(1);
}
}``````

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