Skip to main content

CODILITY: Determine whether given string of parentheses is properly nested.

Task description
A string S consisting of N characters is called properly nested if:
  • S is empty;
  • S has the form "(U)" where U is a properly nested string;
  • S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function:
class Solution { public int solution(String S); }
that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.
For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Assume that:
  • N is an integer within the range [0..1,000,000];
  • string S consists only of the characters "(" and/or ")".
Complexity:
  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(1) (not counting the storage required for input arguments).



class Solution { public int solution(String S) { // write your code in Java SE 8 // write your code in Java SE 8 char[] chrArray=S.toCharArray(); int len=chrArray.length; int closeParan=0; int openParan=0; int retV=0; int pos=0; for(int i=len-1;i>=0;i--){ if(chrArray[i]==')'){ closeParan++; pos=i; }else if(chrArray[i]=='(' && i<pos){ openParan++; } if(closeParan==openParan){ closeParan=openParan=0; } } if(closeParan==openParan) retV=1; return retV; } }

75%                                75 out of 100 points




Analysis summary
The following issues have been detected: wrong answers.
For example, for the input '())(()' the solution returned a wrong answer (got 1 expected 0). 

Comments

  1. UnknownAugust 20, 2020 at 12:05 AM

    // you can also use imports, for example:
    import java.util.*;

    // you can write to stdout for debugging purposes, e.g.
    // System.out.println("this is a debug message");

    class Solution {
    public int solution(String S) {
    // write your code in Java SE 8
    char[] ch=S.toCharArray();
    if(ch.length % 2 ==1 )
    return 0;
    Stack op = new Stack<>();
    for(char c :ch ){
    if(c == '(')
    {
    op.push(c);
    }
    if(c == ')' && !op.isEmpty())
    {
    op.pop();
    }

    }
    return op.isEmpty()?1:0;
    }
    }

    ReplyDelete

Post a Comment

Popular posts from this blog

change directory (cd) function for an abstract file system ( Java Implementation )

Write a function that provides change directory (cd) function for an abstract file system. Notes: Root path is '/'. Path separator is '/'. Parent directory is addressable as "..". Directory names consist only of English alphabet letters (A-Z and a-z). For example, new Path("/a/b/c/d").cd("../x").getPath() should return "/a/b/c/x". Note: The evaluation environment uses '\' as the path separator. public class Path {     private String path;     public Path(String path) {         this.path = path;     }     public String getPath() {         return path;     }     public Path cd(String newPath) {         //throw new UnsupportedOperationException("Waiting to be implemented."); String[] newP=newPath.split("/");     String[] oldP=path.split("/");     int lnCount=0;     for(String str:newP){     if(st...
6 comments
Read more

Distinct: Compute number of distinct values in an array.

Task description Write a function class Solution { public int solution(int[] A); } that, given a zero-indexed array A consisting of N integers, returns the number of distinct values in array A. Assume that: N is an integer within the range [ 0 .. 100,000 ]; each element of array A is an integer within the range [ −1,000,000 .. 1,000,000 ]. For example, given array A consisting of six elements such that: A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1 the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3. Complexity: expected worst-case time complexity is O(N*log(N)); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified. class Solution { public int solution ( int [] A) { // write your code in Java SE 8 int len=A.length; int count= 1 ; ...
1 comment
Read more