Bracket Matching

Account Required

This lesson is available if you sign in.
If you don't have an account, you can sign up for free.

Bracket Matching

Sign in to access this content

You must sign in to access this content.
If you don't have an account you can sign up for free!

Problem

/**
* Given an @param input string, and an opening parenthesis @param openingIndex,
* return the corresponding closing parenthesis index if any (or return `null`)
* Example:
* `Betty (had (a bit) of butter (but the (butter))) was bitter`
* input ^ should return ^
*/
export function getClosingParenthesis(input: string, openingIndex: number): number | null {

}

Solution

/**
* Given an @param input string, and an opening parenthesis @param openingIndex,
* return the corresponding closing parenthesis index if any (or return `null`)
* Example:
* `Betty (had (a bit) of butter (but the (butter))) was bitter`
* input ^ should return ^
*/
export function getClosingParenthesis(input: string, openingIndex: number): number | null {
if (input.length <= openingIndex) throw new Error('Out of bounds opening index');
if (input[openingIndex] != '(') throw new Error('No parenthesis at opening index');

let nestedOpened = 0;
for (let index = openingIndex + 1; index < input.length; index++) {
const char = input[index];
if (char == '(') {
nestedOpened++;
} else if (char == ')') {
if (nestedOpened == 0) {
return index;
}
nestedOpened--;
}
}

return null;
}

Transcript

00:00 Scoring interviews go.

00:01 Today's is not particularly challenging,

00:03 but it is my preferred form of question

00:05 where it is not testing you for some magical intuition

00:07 and instead focuses on basic programming skills.

00:10 So let's jump in and have a look.

00:13 Here we have a very basic problem statement.

00:15 Given an input string

00:16 and an opening parenthesis index, we have

00:19 to return the corresponding closing index, if any,

00:22 otherwise, we will return now.

00:24 Now, as we've mentioned before, when starting out,

00:27 if an example is not given, it's a great idea

00:29 to verify our assumptions by writing down an example.

00:33 Here we have an input string

00:34 and given an index pointing to the first bracket,

00:37 we should return the corresponding closing bracket.

00:40 The key thing to note over here is that between the opening

00:42 and the closing, there might be multiple nested opening

00:45 and closing sections.

00:46 For example, a bit is one section,

00:49 but the butter is one section,

00:50 and butter itself is another section.

00:53 Now let's start writing code.

00:54 Based on the things that we know, we are going

00:57 to have a function that is going to take an input string

01:00 and an opening ES index,

01:02 and then we'll return a closing princess index if found.

01:05 Otherwise, it'll return now.

01:08 Now, before we start fleshing out the body

01:09 with the actual search, we are going

01:11 to write the worst case scenario where nothing is found

01:13 by simply returning.

01:14 Now that's one case handled.

01:17 Now let's take a step back

01:18 and think about the search we have

01:20 to return when we find a closing bracket,

01:23 but only if the number of closing

01:25 and opening brackets between our start

01:27 and end matches up exactly.

01:29 We create a variable to maintain this unclosed opened nested

01:33 index, and then start our loop at the opening index plus one

01:37 and terminate before the end of the string.

01:39 And in each iteration, look at the current character.

01:43 Now, if this character is an opening es,

01:45 then we've essentially started a new nested section

01:47 and we incremented the nested open count.

01:50 A device fits a closing Es,

01:52 and we don't have any nested open sections.

01:54 Then congratulations, we found a closing index.

01:58 Otherwise, we are simply closing off an already opened

02:01 nested section, and that is it.

02:03 As you can see, it's a bit of code, but it's quite simple.

02:06 There's nothing magical about it,

02:08 but it tests a few simple concepts.

02:10 For example, your ability to maintain account of opened

02:13 and closed S

02:14 and your ability to loop through a portion

02:16 of a string effectively.

02:18 In terms of space complexity,

02:19 we are not maintaining anything beyond the input string,

02:22 so it is a constant O of one.

02:24 And in terms of time complexity, we are simply looping

02:27 through the string, potentially all the way till the end.

02:29 So it's linear time or OFN.

02:32 Now, as an added bonus, just

02:33 to set yourself apart from the competition,

02:35 you can start handling exceptional cases.

02:38 For example, if the opening index is greater than

02:40 or equal to the input string length, then it is clearly out

02:43 of bounds and you can throw a new error.

02:45 And another exceptional case

02:47 that you can potentially talk about is if the opening index

02:50 does not actually point to an opening premises.