Created
February 7, 2018 23:07
-
-
Save jianminchen/295f47e60b037ea7c1e2f89a204b961a to your computer and use it in GitHub Desktop.
Leetcode 301 - remove invalid parentheses - using queue.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Leetcode301_removeInvalidParentheses_UsingQueue | |
{ | |
class Program | |
{ | |
/// <summary> | |
/// code study: | |
/// https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/Share-my-Java-BFS-solution | |
/// Feb. 7, 2018 | |
/// Highlights of the design: | |
/// 1. generate all possible substrings | |
/// 2. check one by one on those substring and see if it is valid or not. | |
/// </summary> | |
/// <param name="args"></param> | |
static void Main(string[] args) | |
{ | |
RunTestcase(); | |
} | |
static void RunTestcase() | |
{ | |
var validStrings = removeInvalidParentheses("()())()"); | |
Debug.Assert(validStrings[0].CompareTo("()()()") == 0 || | |
validStrings[0].CompareTo("(())()") == 0); | |
} | |
public static List<String> removeInvalidParentheses(String s) { | |
var res = new List<string>(); | |
if (s == null) | |
{ | |
return res; | |
} | |
var visited = new HashSet<string>(); | |
var queue = new Queue<string>(); | |
// initialize | |
queue.Enqueue(s); | |
visited.Add(s); | |
var found = false; | |
while (queue.Count > 0) { | |
s = queue.Dequeue(); | |
if (isValid(s)) { | |
res.Add(s); | |
found = true; | |
} | |
if (found) | |
{ | |
continue; | |
} | |
// generate all possible states | |
for (int i = 0; i < s.Length; i++) | |
{ | |
// we only try to remove left or right parenthese | |
var current = s[i]; | |
if (current != '(' && current != ')') | |
{ | |
continue; | |
} | |
// remove current char s[i] | |
var substring = s.Substring(0, i) + s.Substring(i + 1); | |
if (!visited.Contains(substring)) { | |
// for each state, if it's not visited, add it to the queue | |
queue.Enqueue(substring); | |
visited.Add(substring); | |
} | |
} | |
} | |
return res; | |
} | |
// helper function checks if string s contains valid parantheses | |
private static bool isValid(String s) | |
{ | |
int count = 0; | |
for (int i = 0; i < s.Length; i++) | |
{ | |
var c = s[i]; | |
if (c == '(') | |
{ | |
count++; | |
} | |
if (c == ')' && count-- == 0) | |
{ | |
return false; | |
} | |
} | |
return count == 0; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment