Leetcode: Valid parentheses
$begingroup$
https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters
(,),{,},[
and], determine if the input string is valid.
For an input string to be valid:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is considered valid.
Example 1:
Input:
()
Output: true
Example 2:
Input:
(){}
Output: true
Example 3:
Input:
(]
Output: false
Example 4:
Input:
([)]
Output: false
Example 5:
Input:
{}
Output: true
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StackQuestions
{
[TestClass]
public class ValidParentheses
{
[TestMethod]
public void OpenOpenClosedClosedMixTest()
{
string input = "([)]";
bool result = IsValid(input);
Assert.IsFalse(result);
}
[TestMethod]
public void OnePairTest()
{
string input = "()";
bool result = IsValid(input);
Assert.IsTrue(result);
}
public bool IsValid(string s)
{
Stack<char> myStack = new Stack<char>();
foreach (var curr in s)
{
if (curr == '(')
{
myStack.Push(curr);
}
else if (curr == '[')
{
myStack.Push(curr);
}
else if (curr == '{')
{
myStack.Push(curr);
}
else if (curr == ')')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '(')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == ']')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '[')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == '}')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '{')
{
return false;
}
}
else
{
return false;
}
}
}
return myStack.Count == 0;
}
}
}
Please review coding style as it was a job interview with 30 minutes to code.
c# programming-challenge interview-questions stack
edited Jan 29 at 14:55
Toby Speight
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
$endgroup$
add a comment |
$begingroup$
https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters
(,),{,},[
and], determine if the input string is valid.
For an input string to be valid:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is considered valid.
Example 1:
Input:
()
Output: true
Example 2:
Input:
(){}
Output: true
Example 3:
Input:
(]
Output: false
Example 4:
Input:
([)]
Output: false
Example 5:
Input:
{}
Output: true
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StackQuestions
{
[TestClass]
public class ValidParentheses
{
[TestMethod]
public void OpenOpenClosedClosedMixTest()
{
string input = "([)]";
bool result = IsValid(input);
Assert.IsFalse(result);
}
[TestMethod]
public void OnePairTest()
{
string input = "()";
bool result = IsValid(input);
Assert.IsTrue(result);
}
public bool IsValid(string s)
{
Stack<char> myStack = new Stack<char>();
foreach (var curr in s)
{
if (curr == '(')
{
myStack.Push(curr);
}
else if (curr == '[')
{
myStack.Push(curr);
}
else if (curr == '{')
{
myStack.Push(curr);
}
else if (curr == ')')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '(')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == ']')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '[')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == '}')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '{')
{
return false;
}
}
else
{
return false;
}
}
}
return myStack.Count == 0;
}
}
}
Please review coding style as it was a job interview with 30 minutes to code.
c# programming-challenge interview-questions stack
edited Jan 29 at 14:55
Toby Speight
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
$endgroup$
$begingroup$
ShouldIsValidReview(")("));be true?
$endgroup$
– aloisdg
Jan 29 at 12:58
add a comment |
$begingroup$
https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters
(,),{,},[
and], determine if the input string is valid.
For an input string to be valid:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is considered valid.
Example 1:
Input:
()
Output: true
Example 2:
Input:
(){}
Output: true
Example 3:
Input:
(]
Output: false
Example 4:
Input:
([)]
Output: false
Example 5:
Input:
{}
Output: true
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StackQuestions
{
[TestClass]
public class ValidParentheses
{
[TestMethod]
public void OpenOpenClosedClosedMixTest()
{
string input = "([)]";
bool result = IsValid(input);
Assert.IsFalse(result);
}
[TestMethod]
public void OnePairTest()
{
string input = "()";
bool result = IsValid(input);
Assert.IsTrue(result);
}
public bool IsValid(string s)
{
Stack<char> myStack = new Stack<char>();
foreach (var curr in s)
{
if (curr == '(')
{
myStack.Push(curr);
}
else if (curr == '[')
{
myStack.Push(curr);
}
else if (curr == '{')
{
myStack.Push(curr);
}
else if (curr == ')')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '(')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == ']')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '[')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == '}')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '{')
{
return false;
}
}
else
{
return false;
}
}
}
return myStack.Count == 0;
}
}
}
Please review coding style as it was a job interview with 30 minutes to code.
c# programming-challenge interview-questions stack
edited Jan 29 at 14:55
Toby Speight
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
$endgroup$
https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters
(,),{,},[
and], determine if the input string is valid.
For an input string to be valid:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is considered valid.
Example 1:
Input:
()
Output: true
Example 2:
Input:
(){}
Output: true
Example 3:
Input:
(]
Output: false
Example 4:
Input:
([)]
Output: false
Example 5:
Input:
{}
Output: true
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StackQuestions
{
[TestClass]
public class ValidParentheses
{
[TestMethod]
public void OpenOpenClosedClosedMixTest()
{
string input = "([)]";
bool result = IsValid(input);
Assert.IsFalse(result);
}
[TestMethod]
public void OnePairTest()
{
string input = "()";
bool result = IsValid(input);
Assert.IsTrue(result);
}
public bool IsValid(string s)
{
Stack<char> myStack = new Stack<char>();
foreach (var curr in s)
{
if (curr == '(')
{
myStack.Push(curr);
}
else if (curr == '[')
{
myStack.Push(curr);
}
else if (curr == '{')
{
myStack.Push(curr);
}
else if (curr == ')')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '(')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == ']')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '[')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == '}')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '{')
{
return false;
}
}
else
{
return false;
}
}
}
return myStack.Count == 0;
}
}
}
Please review coding style as it was a job interview with 30 minutes to code.
c# programming-challenge interview-questions stack
c# programming-challenge interview-questions stack
edited Jan 29 at 14:55
Toby Speight
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
edited Jan 29 at 14:55
Toby Speight
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
edited Jan 29 at 14:55
Toby Speight
24.6k740115
edited Jan 29 at 14:55
Toby Speight
24.6k740115
edited Jan 29 at 14:55
Toby Speight
24.6k740115
24.6k740115
asked Jan 29 at 7:05
GiladGilad
1,38331629
asked Jan 29 at 7:05
GiladGilad
1,38331629
asked Jan 29 at 7:05
GiladGilad
1,38331629
1,38331629
$begingroup$
ShouldIsValidReview(")("));be true?
$endgroup$
– aloisdg
Jan 29 at 12:58
add a comment |
$begingroup$
ShouldIsValidReview(")("));be true?
$endgroup$
– aloisdg
Jan 29 at 12:58
$begingroup$
Should
IsValidReview(")(")); be true?$endgroup$
– aloisdg
Jan 29 at 12:58
$begingroup$
Should
IsValidReview(")(")); be true?$endgroup$
– aloisdg
Jan 29 at 12:58
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.
The name myStack doesn't say much, so I have changed it to something more meaningful in the context.
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
$endgroup$
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
$begingroup$
@Voile I'd argue against usingdefaultas a catch-all to cover the last three cases.defaultshould be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a generaldefaultfor invalid input handling, though.
$endgroup$
– Abion47
Jan 29 at 23:27
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
|
show 3 more comments
$begingroup$
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
Try it Online!
answered Jan 29 at 12:54
aloisdgaloisdg
323211
$endgroup$
$begingroup$
Just to add, you may also use an array of Tuple instead.var (opening, closing) = ('(', ')')should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.
$endgroup$
– user29920
Jan 29 at 22:25
1
$begingroup$
I disagree that using aDictionaryoffers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.
$endgroup$
– Abion47
Jan 29 at 23:31
1
$begingroup$
Sure, theswitchsolution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable
$endgroup$
– somebody
Jan 30 at 5:35
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity ofO(n^2), the other solution has a time complexity ofO(n). You can achieve a better time complexity using a multi-key dictionary
$endgroup$
– Node.JS
Jan 30 at 6:06
|
show 2 more comments
$begingroup$
A couple of small things to add:
Maybe not applicable to a timed interview, but inline documentation (
///) on public members is always nice, and would help to explain the otherwise vagueIsValidmethod name.I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only
(){}will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles<>as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).Any reason the method isn't
static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.That's a very limited set of test-cases: you don't test for
{}at all.
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212445%2fleetcode-valid-parentheses%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.
The name myStack doesn't say much, so I have changed it to something more meaningful in the context.
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
$endgroup$
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
$begingroup$
@Voile I'd argue against usingdefaultas a catch-all to cover the last three cases.defaultshould be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a generaldefaultfor invalid input handling, though.
$endgroup$
– Abion47
Jan 29 at 23:27
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
|
show 3 more comments
$begingroup$
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.
The name myStack doesn't say much, so I have changed it to something more meaningful in the context.
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
$endgroup$
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
$begingroup$
@Voile I'd argue against usingdefaultas a catch-all to cover the last three cases.defaultshould be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a generaldefaultfor invalid input handling, though.
$endgroup$
– Abion47
Jan 29 at 23:27
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
|
show 3 more comments
$begingroup$
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.
The name myStack doesn't say much, so I have changed it to something more meaningful in the context.
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
$endgroup$
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.
The name myStack doesn't say much, so I have changed it to something more meaningful in the context.
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
answered Jan 29 at 10:07
Henrik HansenHenrik Hansen
7,44511128
7,44511128
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
$begingroup$
@Voile I'd argue against usingdefaultas a catch-all to cover the last three cases.defaultshould be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a generaldefaultfor invalid input handling, though.
$endgroup$
– Abion47
Jan 29 at 23:27
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
|
show 3 more comments
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
$begingroup$
@Voile I'd argue against usingdefaultas a catch-all to cover the last three cases.defaultshould be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a generaldefaultfor invalid input handling, though.
$endgroup$
– Abion47
Jan 29 at 23:27
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
1
1
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
$begingroup$
Cool thanks I was wondering if switch case is the way to go or not
$endgroup$
– Gilad
Jan 29 at 10:52
1
1
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
$begingroup$
@Gilad I think a Dictionary would suit well. Check my answer too.
$endgroup$
– aloisdg
Jan 29 at 12:59
1
1
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
$begingroup$
@Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job!
$endgroup$
– Gilad
Jan 29 at 20:54
3
3
$begingroup$
@Voile I'd argue against using
default as a catch-all to cover the last three cases. default should be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a general default for invalid input handling, though.$endgroup$
– Abion47
Jan 29 at 23:27
$begingroup$
@Voile I'd argue against using
default as a catch-all to cover the last three cases. default should be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a general default for invalid input handling, though.$endgroup$
– Abion47
Jan 29 at 23:27
2
2
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
$begingroup$
@solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always.
$endgroup$
– Gilad
Jan 30 at 5:19
|
show 3 more comments
$begingroup$
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
Try it Online!
answered Jan 29 at 12:54
aloisdgaloisdg
323211
$endgroup$
$begingroup$
Just to add, you may also use an array of Tuple instead.var (opening, closing) = ('(', ')')should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.
$endgroup$
– user29920
Jan 29 at 22:25
1
$begingroup$
I disagree that using aDictionaryoffers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.
$endgroup$
– Abion47
Jan 29 at 23:31
1
$begingroup$
Sure, theswitchsolution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable
$endgroup$
– somebody
Jan 30 at 5:35
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity ofO(n^2), the other solution has a time complexity ofO(n). You can achieve a better time complexity using a multi-key dictionary
$endgroup$
– Node.JS
Jan 30 at 6:06
|
show 2 more comments
$begingroup$
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
Try it Online!
answered Jan 29 at 12:54
aloisdgaloisdg
323211
$endgroup$
$begingroup$
Just to add, you may also use an array of Tuple instead.var (opening, closing) = ('(', ')')should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.
$endgroup$
– user29920
Jan 29 at 22:25
1
$begingroup$
I disagree that using aDictionaryoffers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.
$endgroup$
– Abion47
Jan 29 at 23:31
1
$begingroup$
Sure, theswitchsolution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable
$endgroup$
– somebody
Jan 30 at 5:35
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity ofO(n^2), the other solution has a time complexity ofO(n). You can achieve a better time complexity using a multi-key dictionary
$endgroup$
– Node.JS
Jan 30 at 6:06
|
show 2 more comments
$begingroup$
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
Try it Online!
answered Jan 29 at 12:54
aloisdgaloisdg
323211
$endgroup$
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
Try it Online!
answered Jan 29 at 12:54
aloisdgaloisdg
323211
edited Jan 30 at 14:53
answered Jan 29 at 12:54
aloisdgaloisdg
323211
answered Jan 29 at 12:54
aloisdgaloisdg
323211
answered Jan 29 at 12:54
aloisdgaloisdg
323211
323211
$begingroup$
Just to add, you may also use an array of Tuple instead.var (opening, closing) = ('(', ')')should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.
$endgroup$
– user29920
Jan 29 at 22:25
1
$begingroup$
I disagree that using aDictionaryoffers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.
$endgroup$
– Abion47
Jan 29 at 23:31
1
$begingroup$
Sure, theswitchsolution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable
$endgroup$
– somebody
Jan 30 at 5:35
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity ofO(n^2), the other solution has a time complexity ofO(n). You can achieve a better time complexity using a multi-key dictionary
$endgroup$
– Node.JS
Jan 30 at 6:06
|
show 2 more comments
$begingroup$
Just to add, you may also use an array of Tuple instead.var (opening, closing) = ('(', ')')should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.
$endgroup$
– user29920
Jan 29 at 22:25
1
$begingroup$
I disagree that using aDictionaryoffers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.
$endgroup$
– Abion47
Jan 29 at 23:31
1
$begingroup$
Sure, theswitchsolution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable
$endgroup$
– somebody
Jan 30 at 5:35
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity ofO(n^2), the other solution has a time complexity ofO(n). You can achieve a better time complexity using a multi-key dictionary
$endgroup$
– Node.JS
Jan 30 at 6:06
$begingroup$
Just to add, you may also use an array of Tuple instead.
var (opening, closing) = ('(', ')') should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.$endgroup$
– user29920
Jan 29 at 22:25
$begingroup$
Just to add, you may also use an array of Tuple instead.
var (opening, closing) = ('(', ')') should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic.$endgroup$
– user29920
Jan 29 at 22:25
1
1
$begingroup$
I disagree that using a
Dictionary offers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.$endgroup$
– Abion47
Jan 29 at 23:31
$begingroup$
I disagree that using a
Dictionary offers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code.$endgroup$
– Abion47
Jan 29 at 23:31
1
1
$begingroup$
Sure, the
switch solution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
Sure, the
switch solution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable$endgroup$
– somebody
Jan 30 at 5:35
1
1
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common
$endgroup$
– somebody
Jan 30 at 5:35
$begingroup$
@aloisdg your solution has a time complexity of
O(n^2), the other solution has a time complexity of O(n). You can achieve a better time complexity using a multi-key dictionary$endgroup$
– Node.JS
Jan 30 at 6:06
$begingroup$
@aloisdg your solution has a time complexity of
O(n^2), the other solution has a time complexity of O(n). You can achieve a better time complexity using a multi-key dictionary$endgroup$
– Node.JS
Jan 30 at 6:06
|
show 2 more comments
$begingroup$
A couple of small things to add:
Maybe not applicable to a timed interview, but inline documentation (
///) on public members is always nice, and would help to explain the otherwise vagueIsValidmethod name.I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only
(){}will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles<>as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).Any reason the method isn't
static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.That's a very limited set of test-cases: you don't test for
{}at all.
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
$endgroup$
add a comment |
$begingroup$
A couple of small things to add:
Maybe not applicable to a timed interview, but inline documentation (
///) on public members is always nice, and would help to explain the otherwise vagueIsValidmethod name.I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only
(){}will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles<>as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).Any reason the method isn't
static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.That's a very limited set of test-cases: you don't test for
{}at all.
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
$endgroup$
add a comment |
$begingroup$
A couple of small things to add:
Maybe not applicable to a timed interview, but inline documentation (
///) on public members is always nice, and would help to explain the otherwise vagueIsValidmethod name.I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only
(){}will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles<>as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).Any reason the method isn't
static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.That's a very limited set of test-cases: you don't test for
{}at all.
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
$endgroup$
A couple of small things to add:
Maybe not applicable to a timed interview, but inline documentation (
///) on public members is always nice, and would help to explain the otherwise vagueIsValidmethod name.I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only
(){}will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles<>as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).Any reason the method isn't
static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.That's a very limited set of test-cases: you don't test for
{}at all.
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
answered Jan 29 at 11:20
VisualMelonVisualMelon
3,5071025
3,5071025
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212445%2fleetcode-valid-parentheses%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Should
IsValidReview(")("));be true?$endgroup$
– aloisdg
Jan 29 at 12:58