DEV Community: codechunker

I didn’t know how to solve this Leetcode Problem!😭😭😭

codechunker — Wed, 13 May 2020 23:27:58 +0000

This is a medium Leetcode 402 question where you are asked to remove k digits from a number to make that number the smallest possible number. See problem description below:

The question is quite understandable and straight forward but the issue is with knowing the numbers to remove. At first, I thought that sorting the numbers and keeping track of the positions and then removing the largest numbers would work but apparently that didn’t work.

After trying to no avail, I had to seek for solution online and came across two algorithms:

FIRST ALGORITHM

public static String removeKdigits(String num, int k) {
    Stack<Character> stack = new Stack<>();
    StringBuilder answer = new StringBuilder();
    if (num.length() == k) return "0";

  for (int i = 0; i < num.length(); i++) {
   while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
            stack.pop();
            k = k - 1;
        }
        stack.push(num.charAt(i));
    }

    while (!stack.isEmpty()) {
        answer.append(stack.pop());
    }

    if (!answer.toString().isEmpty()) {
        answer = answer.reverse();
        String s = answer.toString().replaceFirst("^0+(?!$)", "");
        if (k != 0)
            s = s.substring(0, answer.length() - k);
        return s;
    } else
        return "0";
}

To understand the algorithm above, please check thecodingworld on YouTube. He did a good job to explain the algorithm. His code was written in Python, so I had to translate to Java.

SECOND ALGORITHM

public static String  removeKdigits(String num, int k) {
    Stack<Character> stack =  new Stack<>();
    int length = num.length();
  for (int i = 0; i < length; i++) {
   while (!stack.isEmpty() && k > 0 && stack.peek() > num.charAt(i)) {
            stack.pop();
            k -= 1;
        }

        if (!stack.isEmpty() || num.charAt(i) != '0')
            stack.push(num.charAt(i));
    }

    //Now remove the largest values from the top of the stack
    while (!stack.empty() && k != 0) {
        stack.pop();
        k--;
    }


    if (stack.isEmpty())
        return "0";

    //now retrieve the number from stack into a string
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.reverse().toString();
}

Also to understand the second algorithm above, please check Tech Dose for the explanation. I also translated the code to Java.

OBSERVATION

I have learnt a lot from these algorithms especially from the way people think and I think that’s the fun of solving algorithm questions.
Thank you for reading. Please leave a comment or suggestion below.

The Good, The Bad and The Ugly Solutions to Leetcode’s Single Element in a Sorted Array

codechunker — Tue, 12 May 2020 20:20:30 +0000

This is a medium Leetcode 543 question. You are given an array of integers of which all elements in the array appear twice except one. The question is to get the one that does not have any duplicate (i.e appeared just once). See problem description below:

NOTE: The solution should be in O(log n) and O(1) space.
The above problems can be solved in so many ways but I will talk about three ways to solve it in decreasing order of performance.

FIRST ALGORITHM (THE UGLY)

The first solution that came to my mind was to use a HashMap. There is a saying that goes thus;

For every question you encounter, always think HashMaps, there is a probability that you will solve the problem with HasMap 😂😂😂.

The idea is to store the count of elements in the array inside a HashMap with the element as the key and the count as the value.

Then next step is to loop through return the key that its value is 1 because if the value is 1, definitely that’s the odd one. The code is shown below:

public int singleNonDuplicateUsingHashMap(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();

    //store the count of each element in the map
    for (int i = 0; i < nums.length; i++) {
        if (!map.containsKey(nums[i])) {
            //if the key doesn't exist, create a new one
            map.put(nums[i], 1);
        }else {
          //update the count of the existing by incrementing it by 1
            map.put(nums[i], map.get(nums[i]) + 1);
        }
    }

    //loop through map and get the one that has the value of 1
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    return -1;

}

The above code works just fine but the runtime is O(n) for each of the loops which translates to O(n) + O(n) which is equal to 2O(n). 2O(n) is the same as O(n) because we don’t consider constants in calculating runtime. To make this slightly better, let’s look at another algorithm.

SECOND ALGORITHM (THE BAD)

1.Loop through the array by incrementing the count by two (2);

2.check if the current element is equal to the next element;

3.if they are not, that means that current element is the odd one without a duplicate. See the steps in the image below;

STEPS

The first step starts from element at index 0(i=0), checks if the next element at index(i+1) is the same. Since they are the same, it increments the index (i) by 2. It follows the same process for Step 2.
For step 3 which is at index 4, it checks and finds out they are not the same, so it returns value at the current index (i=4)which is 10. The code is shown below:

public int singleNonDuplicateLinearly(int[] nums) {
    if (nums.length == 1) return nums[0];
    for (int i = 0; i < nums.length; i+=2) {
        if (i == nums.length - 1) return nums[i];
        if (i+1 < nums.length && nums[i] != nums[i+1]) {
            return nums[i];
        }
    }
    return -1;
}

THIRD ALGORITHM (THE GOOD😎😎😎)

If you look at the problem description, it says that the runtime should be O(log n) and space complexity of O(1).

Whenever you see a question that says runtime should be O(log n) and space complexity of O(1), just know that the solution would probably involve Binary Search.

As with every binary search, it starts from the middle (divide the array into two halves);
checks the right half elements to know if they are even number of elements left. if they are even (stores the state in a variable (isEven)), there is no way the odd number would be in the second half if they are even.
From the element at middle, it checks the element before it to know if they are equal.
If they are equal and the variable isEven is true, it moves the right arrow to be at two elements before the middle element (mid-2). if the variable isEven is false, it moves the left arrow to start from an element after the middle element (mid+1).
If they are not equal, and isEven is true, it moves the left arrow to two elements after the middle element. If they are not equal, it right arrow to an element before the middle element.

public static int singleNonDuplicateUsingBinarySearch(int[] nums) {
   int lowLeft = 0;
   int highRight = nums.length-1;
   boolean isEven;

   while (highRight > lowLeft) {
       int mid = lowLeft + (highRight - lowLeft) /2;
       //check if the right side is even
       isEven = (highRight - mid) % 2 == 0;

       if (nums[mid] == nums[mid-1]) {
           if (isEven) {
               highRight = mid - 2;
           }else {
               lowLeft = mid + 1;
           }
       }else if (nums[mid] == nums[mid + 1]){
           if (isEven) {
               lowLeft = mid + 2;
           }else {
               highRight = mid - 1;
           }

       }else  {
           return nums[mid];
       }

   }
   return nums[lowLeft];
}

Thank you for reading. Please drop a comment.

Solution to Leetcode's Flood Fill Question (interesting Question)

codechunker — Tue, 12 May 2020 01:14:32 +0000

This is an easy Leetcode 733 problem. See problem description below:

Question Explanation

To get a clearer picture of what the question wants us to do, first, it will be better to break the multidimensional array elements to form a square-like structure e.g the picture below shows the break down of [[1,1,1], [1,1,0], [1,0,1]]:

Now that we have broken the elements into rows and columns as shown in the figure above, the explanation of the question is this; given a particular starting row (sr) and a starting column(sc) which is suppose to be the starting pixel and given a new color (newColor) which is to be used to replace, change that starting pixel (sr, sc) to the new color (newColor) and also change its neigbours (4-directional to the starting pixel which is of the same colour).

For example, assuming the circled number in the image above is the starting index, the image below shows exactly the steps that will be taken to flood fill:

NOTE: The colored numbers/pixels are the neigbours (4-directional)of the circled numbers/pixels.

STEPS

So Step 1 starts from the middle as the starting pixel, changes itself to the new colour which is ‘2’ in this case. It checks its neighbours (left, right, top, bottom), replaces those that had the same number as the one the starting pixel had (which is 1)before it changed to the new colour (2). So it changes all the 1s to 2s as long as they are neighbours. it then moves the ‘batton’ to its left neighbour (1st column)to go through the same process.

Step 2, changes its top and bottom neigbours to 2 because those neighbours had the same number as its initial before itself was changed. NOTE that step 2 does not have a left neighbour.

Step 3 and 4 go through the same process.

if you noticed, the left and right neigbours can be considered as the columns while the top and bottom can be considered as the rows.
ALGORITHM
The first idea that comes to the mind in this kind of problem is Recursion.
We need to keep a track of the initial colour and then use recursion to go through all the paths.

The source code is shown below:

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) return image;

        flood(image, image[sr][sc], newColor, sr, sc);

        return image;
    }

public void flood(int[][] image, int color, int newColor, int sr, int sc) {
        if (sr < 0 || sc < 0 ||  sr >= image.length || sc >= image[0].length || image[sr][sc] != color) {
            return;
        }

        image[sr][sc] = newColor;

        int topRowNeighbour = sr - 1;
        int bottomRowNeighbour = sr + 1;
        int leftColumnNeigbour = sc - 1;
        int rightColumnNeighbour = sc + 1;

        flood(image, color, newColor, topRowNeighbour, sc );
        flood(image, color, newColor, bottomRowNeighbour, sc );
        flood(image, color, newColor, sr, leftColumnNeigbour );
        flood(image, color, newColor, sr, rightColumnNeighbour );
    }
}

Thank you very much for reading. Please leave a comment or suggestion.

Took a while to solve this Leetcode problem. Remove Duplicates From Sorted Array II

codechunker — Sun, 10 May 2020 21:55:21 +0000

I must confess this question took me a while as a beginner. This is a medium Leetcode 80 question. This is similar to Leetcode 26 where you are simply asked to remove all duplicates in an array. The tweak in Leetcode 80 is that the highest duplicate a number in array can have is two e.g [1,1,1,2,2,3] should turn to [1,1,2,2,3]. See problem description below:

This problem took me a while not because i could not solve it with any method I wanted, but I wanted to solve it the way it was described in the question i.e solving it in-place in O(1) space complexity.

See below the rubbish I was trying to do🤣🤣🤣. PLEASE DON’T TRY THIS AT HOME. I won't even bother trying to explain what i was trying to do but if you can understand it, fine and good.

public static int removeDuplicates(int[] nums) {
    //111223 => 11223
    int count = 0;
    int elementCount = 1;

    for (int i = 0; i < nums.length; i++) {
        if (i + 1 < nums.length) {

            if (nums[i] == nums[i + 1] && elementCount < 3) {
                elementCount++;
                nums[count] = nums[i];
                count++;
            }else if (nums[i] == nums[i+1] && elementCount >= 3){
                elementCount++;
                continue;
            }else if (nums[i] != nums[i+1] && elementCount >=3){
                elementCount = 1;
                int temp = nums[i+1];
                nums[count] = temp;
                nums[i+1] = -1;
                count++;
            }else if (nums[i] != nums[i+1] && elementCount < 3){
                elementCount = 1;

                if (nums[i] == -1){
                    nums[count] = nums[i+1];
                    elementCount = 3;
                }

                else nums[count] = nums[i];
                count++;
            }
        }

    }

    return count;

}

THE CORRECT CONCEPT

Since the problem says the maximum duplicates you can have for a number is two (2) and the problem must be solve in-place i.e don’t create a new array rather manipulate the given array. The concept is as follows;

Keep a counter index(indexCount)from the third index (3) this is to be incremented. You do this because no matter what, the first two indices will always be correct. it doesn’t matter if they are the same or different.

From the third index, start comparing the current index to two indices before it. If they are not equal, put the current element (nums[i]) into the current indexCount value and then increment indexCount. Remember, if they are equal, that means the current element is now 3 which violates condition that the maximum duplicate should be 2. The code is shown below:

public static int removeDuplicates(int[] nums) {
    int indexCount = 2;
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] != nums[indexCount-2]) {
            nums[indexCount] = nums[i];
            indexCount++;
        }
    }
    return indexCount;
}

The runtime of the algorithm above is O(n) and the space complexity is O(1) which makes it very efficient especially in terms of space complexity.

Remember always think outside the box
Thank you for reading. Please leave a comment or suggestion.

Solution to Leetcode’s Valid Perfect Square

codechunker — Sat, 09 May 2020 23:34:28 +0000

This is an easy Leetcode problem 367. The question gives a number and you are to write a function to determine if it is a perfect square. See the image below for description.

According to wikipedia, a perfect square is the product of a number with itself. in this context, a perfect square is a number when multiplied by itself will give you the number in question.
There are many ways in solving this problem but I will talk about three in this article.

NOTE: Do not use any library functions like Math.sqrt().

THE NAIVE APPROACH

Of course the naive or brute force approach would be to loop through from 1 to the number, multiplying a number by itself and checking if the product equals the number you are looking for. if it does, then return true, else return false.

public static boolean isPerfectSquareWithBruteForce(int num) {
    if (num == 1) return true;
    for (int i = 1; i < num; i++) {
        if (i*i == num) return true;
    }
    return false;
}

The code above works but can be very slow. its runtime is O(n).
To make this better, we may decide to loop from 1 to half of the number because there is no way you can get the number in question by multiplying number greater than half (i.e num/2) by itself. e.g to determine if 9 is a perfect square, there is no way a number between 4 to 9 would give you 9. So in other words, to know if a number is a perfect square, the number that will multiply itself will have to be in the first half (between 1–3).

 public static boolean isPerfectSquareWithHalfNumber(int num) {
        if (num ==  1 || num ==  0) return true;
        for (int i = num/2; i >= 0; i-- ) {
            if (i*i == num) return true;
        }

        return false;
    }

Technically speaking, it may seem that the above code would make it faster but the truth is , the runtime of this is O(n/2) which still translates to O(n) because in computer science, we don’t consider constants when dealing with runtime.

A FASTER SOLUTION

A better way to solve this problem would be to use Binary Search. This solves the problem by using the divide and conquer methodology. It keeps splitting the number into half and checking if number is found.

public static boolean isPerfectSquareWithBinarySearch(int num) {

    double start = 1;
    double end = num/2;

    if (num == 1) return true;

    while (start <= end) {
        double mid = Math.floor((end - start)/2) + start;

        if (mid * mid ==  num) {
            return true;
        }else if (mid * mid < num) {
            start = mid + 1;
        }else {
            end = mid - 1;
        }
    }
    return false;
}

The runtime of the above is O(log n) which is faster than O(n) linear time.

Thank you for reading and please leave a comment or suggestion.

INTRODUCTION TO REGEX EXPRESSIONS FOR JAVA DEVELOPERS

codechunker — Wed, 29 Apr 2020 17:39:07 +0000

According to oracle doc,
Regular Expressions popularly called Regex are ways to describe a set of strings based on common characteristics shared by each string in the set. They can be used to search, edit, or manipulate text and data.

In layman’s term, Regular Expressions are ways that help you to validate or match strings according to a particular format. In other words, you can use it to check if a particular input by a user is correct or use it to retrieve or extract values that match a particular sequence.

IMPORTANCE/USAGES OF REGEX
• Validate a user’s input.
• Search text in a given data. (can be used in Text Editors)
• Parser in compilers
• Syntax highlighting, packet sniffers etc.

To have a thorough basic understanding of Regex we need to understand the following concepts:

QUANTIFIERS ( * + ? {n} . )
The quantifiers in Java ( and in most programming languages) consists of , +, ?, {} .
a) * matches zero or more instances of its preceding pattern. e.g. abc* means the text must match 'ab' followed by zero or more of 'c' i.e. the text may not have ‘c’ attached to it and the text may also have one or more ‘c’ . The preceding pattern in this case is ‘ab’. *TRY IT**

b) + matches one or more instances of its preceding pattern e.g abc+ means that the text must have ‘ab’ followed by one or more ‘c’. so abc is the least you can have that is correct, abcc is also correct. TRY IT

c) ? matches zero or one occurrences of the pattern e.g abc? Means the text can either be abc or ab. TRY IT.

d) {n} matches the exact number (n) specified in the expression. e.g a{2}bc means that you can only have two ‘a’ followed by one ‘b’ and one ‘c’. TRY IT

e) {n, } matches at least the number specified. That means you must have n number or more of the preceding expression e.g ab{2,}c means you must have a, followed by two or more ‘b’ and then c. TRY IT

f) {n,m} matches between n and m (inclusive) of the pattern. This means you can have between to m occurrences of the preceding pattern. e.g ab{2,5}c means abbc, abbbc, abbbbc, abbbbbc are all correct. Anything out of these is wrong. TRY IT.

g) ‘.’ matches all non-white space characters

OPERATORS(| [] ^ )
Pipe (|) is used as ‘OR’. So it matches the expression on the left or the expression on the right. e.g abc|abd means the text should be either abc or abd. TRY IT.

[] means the text should match any of the characters in the angle brackets e.g a[bc] means the text should be ‘a’ followed by either ‘b’ or ‘c’.
[0-9]% means the text should be any number from 0 to 9 followed by ‘%’
[a-zA-Z] means any character as long as it between a-z or A-Z.
[abc] means the text or string should be either a, or b or c.
Adding ‘^’ to any of the expressions negates the meaning of that expression e.g [^abc] means the string should be any character as long as it is not a or b or c. TRY IT.

GROUPING AND BACK REFERENCES
Another interesting thing about regex is that you can group your expressions and probably reuse them when necessary. To group elements in expressions, use round brackets e.g ().
A Back Reference stores the part of the string that matched the group. You can reference a particular group by using the sign $. $1, $2…represent group 1, group 2 etc. the default group is $0 which is the actual text itself. For example, lets remove all the spaces in a sentence .The regex for this example would be the code snippet below:

private static String backReference(String text) {
    String pattern = "(\\w+)([\\s])";
    return text.replaceAll(pattern, "$1");
}

The expression in the code above has 2 groups: (\w+) and (\s). So we are saying the text has to be a bunch of words(\w+) and spaces(\s+). After that, we replace the whole text with just group 1($1) which will just remove the spaces because all we need now is just words. Referencing $1 in the back referencing.

NOTE: In java, we need to escape the character class (\w and \s) with another slash otherwise you would have a syntax error.

LOOK AHEAD/LOOK BEHIND
This is a way to exclude a pattern. So you can say a string should be valid only if it doesn’t come before a particular string and vice versa. e.g. abc(?=d) will match ‘abc’ as long as it follows a ‘d’. but note that ‘d’ will be excluded. TRY IT.
A good real life application of this would be to get the value in any HTML tag e.g <h1>Hello World</h1>. The expression would be (?i)(<h1.*?>)(.*(?=<))() TRY IT. This returns Hello World
You can also use (?!pattern) as a negative look ahead e.g ab(?!c) will match ab if ‘ab’ is not followed by ‘b’.

GREEDY AND LAZY
The quantifiers above are said to be greedy in the sense that they’ll match as many occurrences as long as the match is still successful. e.g for the regex a.+c, you would expect it to mean the text should be ‘a’ followed by one or more non-white space character. So you would expect a possible match to be ‘abcccd’ or ‘abcc’ or ‘abbc’ as individual results. This is meant to be true but because of the greedy attitude, it will grab all the texts (abcccd abcc abbc) as one and return ‘abcccd abcc abbc’ as one result because if you notice, the first character is ‘a’ followed by one or more of any other character and it now ends with c which matches exactly a.+c

In order to restrict this “greedy attitude”, just add question mark (?) in front of the quantifier, this makes the quantifier a bit reluctant which means it will match as few occurrences as possible as long as the match is successful. So ab.+?c would return the results individually instead of grabbing the whole string and processing them as one. TRY IT.

A better application of this would be this: Assuming you want to get just the tags <h1> and </h1> seperately from <h1>Hello World</h1>, you would expect that the regex for it would be <.+> but in reality, it is going to grab the whole text (<h1>Hello World</h1>) and process it as one and still return the same text to you because it actually matches the expression you provided (the text should start with ‘<’, followed by one or more of any other character and then end ‘>’ ) which the text satisfies TRY IT.
Adding ‘?’ in front of the quantifier is sometimes called lazy.

In a nutshell, ‘Greedy’ means match longest possible string while ‘lazy’ means match shortest possible string.

NOTE: Be careful when using these quantifiers especially period(.) in expressions.

CHARACTER CLASSES
A character class is an escape sequence that represents a group of characters. Some predefined characters in java are listed below:

If you notice from the above table, the Uppercase letters negate the functions of the lowercase letters vice versa

NOW OVER TO THE WORLD OF JAVA
String class in Java comes with an inbuilt boolean method called matches that matches a string against a regex.

public static void main(String[] args) {
    String value = "12345";
    System.out.println("The Result is: "+value.matches("\\d{5}"));
}

The code snippet above would return ‘The Result is: true’ because the value (12345) matches exactly 5 characters. Any thing other than 5 would return ‘The Result is: false’.

Apart from matches method of the String class, most of the classes you would need for regex are found in java.util.regex package. They consist of three classes:
• Pattern: this is the compiled representation of of a regular expression. To use this, you must first call the static method (compile) in the pattern class which returns a Pattern object.
• Matcher: This is the engine that that interprets the pattern and performs match operations against an input string. To get an object, you have to invoke the matcher method on a Pattern object.
• PatternSyntaxException: this indicates error in a regular expression pattern

To Match a string using Pattern/Matcher Classes

public static void main(String[] args) {
    String value = "12345";
    String regex = "\\d{5}";
    Pattern pattern = Pattern.compile(regex);
    Matcher matcher = pattern.matcher(value);
    System.out.println("The Result is: "+matcher.matches());
}

Now the question is why would I go through the stress of using Pattern/Matcher when I can just match the string against the regex (value.matches(regex)).
Well the truth is the implementation of method matches in class String using Pattern/Matcher under the hood. So, for every string you match, it creates a Pattern object before matching.

When to use Pattern/Matcher VS String.matches(String text)

public class PatternMatcher {
    public static void main(String[] args) {
        String [] texts = {"nozzle","punjabi","waterlogged","imprison","crux","numismatlogists","sultans","rambles","deprecating","aware","outfield","marlborough","guardrooms","roast","wattage","shortcuts","confidential","reprint","foxtrot","disposseslogsion","floodgate","unfriendliest","semimonthlies","dwellers","walkways","wastrels","dippers","engrlogossing","undertakings"};
         List<String> resultStringMatches = matchUsingStringMatches(texts);
        List<String> resultsPatternMatcher = matchUsingPatternMatcher(texts);
        System.out.println("The Result for String matches is: "+resultStringMatches.toString());
        System.out.println("The Result for pattern/matcher is: "+resultStringMatches.toString());
    }

    private static List<String> matchUsingPatternMatcher(String[] texts) {
        List<String> matchedList = new ArrayList<>();
        String pattern = "[a-zA-Z]*log[a-zA-Z]*";
        Pattern regexPattern = Pattern.compile(pattern);
        Matcher matcher;
        for (int i = 0; i < texts.length; i++) {
             matcher = regexPattern.matcher(texts[i]);
            if (matcher.matches()) {
                matchedList.add(texts[i]);
            }
        }
        return matchedList;
    }

    private static List<String> matchUsingStringMatches(String[] texts) {
        String pattern = "[a-zA-Z]*log[a-zA-Z]*";
        List<String> matchedList = new ArrayList<>();

        for (int i = 0; i < texts.length; i++) {
            //for each time it calls matches(pattern), it creates a pattern object
            if (texts[i].matches(pattern)) {
                matchedList.add(texts[i]);
            }
        }
        return matchedList;
    }
}

The code above matches all the elements in an array against a particular regex ([a-zA-Z]log[a-zA-Z]). The regex is meant to get all texts that have the word “log”. Before a match against a regex, that expression must be compiled (Pattern.compile);
The first method matchUsingPatternMatcher() compiles the pattern first before looking for matches while the second method matchUsingStringMatches() creates a new Pattern Object

(Pattern.compile()) for every element in the array which is expensive/costly and may cause memory leakage especially then the data/texts are too many.
So if you care about performance when dealing with large set of data, use the Pattern/Matcher class to compile first and use the instance to match the texts.

Thank you very much for reading. Please you can leave a comment, suggestion or correction on the comment section below.

INTRODUCTION TO REGEX EXPRESSIONS FOR JAVA DEVELOPERS

codechunker — Tue, 28 Apr 2020 10:54:56 +0000

IMPORTANCE/USAGES OF REGEX
• Validate a user’s input.
• Search text in a given data. (can be used in Text Editors)
• Parser in compilers
• Syntax highlighting, packet sniffers etc.

To have a thorough basic understanding of Regex we need to understand the following concepts:

c) ? matches zero or one occurrences of the pattern e.g abc? Means the text can either be abc or ab. TRY IT.

d) {n} matches the exact number (n) specified in the expression. e.g a{2}bc means that you can only have two ‘a’ followed by one ‘b’ and one ‘c’. TRY IT

g) ‘.’ matches all non-white space characters

OPERATORS(| [] ^ )
Pipe (|) is used as ‘OR’. So it matches the expression on the left or the expression on the right. e.g abc|abd means the text should be either abc or abd. TRY IT.

[] means the text should match any of the characters in the angle brackets e.g a[bc] means the text should be ‘a’ followed by either ‘b’ or ‘c’.
[0-9]% means the text should be any number from 0 to 9 followed by ‘%’
[a-zA-Z] means any character as long as it between a-z or A-Z.
[abc] means the text or string should be either a, or b or c.
Adding ‘^’ to any of the expressions negates the meaning of that expression e.g [^abc] means the strinf should be any character as long as it is not a or b or c. TRY IT.

private static String backReference(String text) {
    String pattern = "(\\w+)([\\s])";
    return text.replaceAll(pattern, "$1");
}

NOTE: In java, we need to escape the character class (\w and \s) with another slash otherwise you would have a syntax error.

In a nutshell, ‘Greedy’ means match longest possible string while ‘lazy’ means match shortest possible string.

NOTE: Be careful when using these quantifiers especially period(.) in expressions.

CHARACTER CLASSES
A character class is an escape sequence that represents a group of characters. Some predefined characters in java are listed below:

If you notice from the above table, the Uppercase letters negate the functions of the lowercase letters vice versa

NOW OVER TO THE WORLD OF JAVA
String class in Java comes with an inbuilt boolean method called matches that matches a string against a regex.

public static void main(String[] args) {
    String value = "12345";
    System.out.println("The Result is: "+value.matches("\\d{5}"));
}

The code snippet above would return ‘The Result is: true’ because the value (12345) matches exactly 5 characters. Any thing other than 5 would return ‘The Result is: false’.

To Match a string using Pattern/Matcher Classes

public static void main(String[] args) {
    String value = "12345";
    String regex = "\\d{5}";
    Pattern pattern = Pattern.compile(regex);
    Matcher matcher = pattern.matcher(value);
    System.out.println("The Result is: "+matcher.matches());
}

When to use Pattern/Matcher VS String.matches(String text)

public class PatternMatcher {
    public static void main(String[] args) {
        String [] texts = {"nozzle","punjabi","waterlogged","imprison","crux","numismatlogists","sultans","rambles","deprecating","aware","outfield","marlborough","guardrooms","roast","wattage","shortcuts","confidential","reprint","foxtrot","disposseslogsion","floodgate","unfriendliest","semimonthlies","dwellers","walkways","wastrels","dippers","engrlogossing","undertakings"};
         List<String> resultStringMatches = matchUsingStringMatches(texts);
        List<String> resultsPatternMatcher = matchUsingPatternMatcher(texts);
        System.out.println("The Result for String matches is: "+resultStringMatches.toString());
        System.out.println("The Result for pattern/matcher is: "+resultStringMatches.toString());
    }

    private static List<String> matchUsingPatternMatcher(String[] texts) {
        List<String> matchedList = new ArrayList<>();
        String pattern = "[a-zA-Z]*log[a-zA-Z]*";
        Pattern regexPattern = Pattern.compile(pattern);
        Matcher matcher;
        for (int i = 0; i < texts.length; i++) {
             matcher = regexPattern.matcher(texts[i]);
            if (matcher.matches()) {
                matchedList.add(texts[i]);
            }
        }
        return matchedList;
    }

    private static List<String> matchUsingStringMatches(String[] texts) {
        String pattern = "[a-zA-Z]*log[a-zA-Z]*";
        List<String> matchedList = new ArrayList<>();

        for (int i = 0; i < texts.length; i++) {
            //for each time it calls matches(pattern), it creates a pattern object
            if (texts[i].matches(pattern)) {
                matchedList.add(texts[i]);
            }
        }
        return matchedList;
    }
}

Thank you very much for reading. Please you can leave a comment, suggestion or correction on the comment section below.

Solution to Leetcode's Contiguous Array

codechunker — Sat, 18 Apr 2020 23:20:20 +0000

This is a medium Leetcode problem 525. See below image for description:

ALGORITHM

Create a map that stores the current count to the index.
Loop through the array, if the current value is 0, subtract 1 from count. if it is 1, add 1 to count.
if the map does not have the current value of count as a key, put the new value in map with key as the current count and the value as the index.
if the map has the current count as key, get the maximum between the current max and (index - value of the key).
return max.

CODE

 public int findMaxLength(int[] nums) {
        int count = 0;
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0)
                count += -1;
            else
                count += 1;

            if (map.containsKey(count))
                max = Math.max(max, i - map.get(count));
            else
                map.put(count, i);

        }

        return max;
    }

Solution to Leetcode’s Maximum Subarray

codechunker — Mon, 23 Mar 2020 11:11:20 +0000

This is an easy Leetcode problem 53. See below image for description:

ALGORITHM

1.Have a global variable currentSum;

2.Have a global variable max that will also be the return value;

3.Loop through the array, check if the current element (nums[i]) is greater than the current sum and current element put together (i.e currentSum + nums[i]);

4.if it is greater, reassign the currentSum variable to be the current element, nums[i];

5.if it is not, reassign the currentSum variable to be the summation of both the existing current sum and the current array element (currentSum = currentSum + nums[i])

6.finally, check if the currentSum is greater than the current maximum. if it is, reassign the current max to be equal to currentSum.

7.Then return max.

CODE

public static int maxSubArray(int[] nums) {

    int currentSum = nums[0];
    int max = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > (currentSum + nums[i]))
            currentSum = nums[i];
        else
            currentSum = currentSum + nums[i];

        if (currentSum > max) {
            max = currentSum;
        }
    }
    return max;
}

OUTCOME

IMPROVEMENT
Math.max checks the maximum/bigger value between two numbers. So we can replace those if statements with Math.max(). Cleaner code is shown below:

IMPROVED CODE

 public static int maxSubArray(int[] nums) {

        int currentSum = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {

            //cleaner and simple
            currentSum = Math.max(nums[i], currentSum + nums[i]);

            max = Math.max(currentSum, max);
        }
        return max;
    }

LESSONS
1.Don’t always be in the box of a particular algorithm you thought would work, just the way i thought Sliding window would work.

2.Using library functions where and when needed.

Thank you for reading. Please leave a comment.

Solution to Leetcode's ZigZag Conversion: My thought process as a beginner

codechunker — Tue, 28 Jan 2020 03:17:14 +0000

This is a medium Leetcode Problem. See below image for description:

ALGORITHM

1.Have a map of a row to a StringBuilder of the characters for that row;
2.Have a global counter (row): the current count of the row as you loop through;
3.boolean variable to know when to increment or decrement the row variable in step 2 above;
4.loop through the string, check if the current count of the global variable row is equal to the number of row; if it is, it should set the increment variable to false; else, it should set the increment variable to true;
5.increment/decrement row variable depending on the current value of the increment variable;
6.check the map for availability of the current row value. if it is not found, put the row with a new StringBuilder object;
7.Get the the value of the current row and append the current character to it;
8.loop through the map, append values to stringbuilder, then return string value of the stringbuilder.

OUTCOME

LESSONS
After checking discussion section on Leetcode, I discovered that there was pattern to use. Learnt a lot from reading other people’s solutions.

What you need to know about Leetcode’s Count and Say: My thought process as a beginner.

codechunker — Mon, 20 Jan 2020 02:02:07 +0000

This is another Leetcode Problem: You are given an integer to generate the nth term of its count and say.The count and say is a way of reading off digits from the previous member. So 1 would read as “One 1” or 11 and 11 would read as “Two 1s” or 21 etc.

ALGORITHM

1.Get the first character of the string. This would serve as the previous;
2.Loop through every other character (i.e from the next character after step 1). This would serve as the next character.
3.Compare if step 1 and 2 (previous and next) are equal.
4.If they are equal, increment the global counter.
5.If they are not equal, append the current value of global counter and the previous character (in that order) into a global result StringBuilder. The previous character now becomes the current next character (previous = next). Then reset global counter (count = 1).
6.Outside the loop, append the global counter and previous to the global result.This is majorly for edge cases.

MY CODE

class Solution {
    public String countAndSay(int n) {
          if (n == 1)
            return "1";
        else {
            return doCounting(countAndSay(n - 1));
        }
    }

    private String doCounting(String value) {
        int length = value.length();
        int count = 1;
        StringBuilder result = new StringBuilder();
        int i;
        char previous = value.charAt(0);//initial
        for (i  = 1; i < length; i++) {
            char next = value.charAt(i);
            if (previous == next) {
                count++;
            }else {
                result.append(count).append(previous);
                previous = next;
                count = 1;//reset
            }
        }
        result.append(count).append(previous);

        return result.toString();
    }
}

OUTCOME

IMPROVEMENT
At first, the solution was a bit slower so I had to scan through to look for a way to make my solution a bit faster. Found out where I got it wrong: For every loop, I was calling value.length(). This should be reusable, so I initialized it to a variable. Did the same thing for charAt(i).
After the cleanups, I got the above scores, which I feel is very OK.

LESSONS
Always initialize some library functions to variable to prevent calling it multiple times e.g, value.length(), value.charAt(i) etc. I’m sure you get the point. This also applies to Object creations or instances.

CONCLUSION
I hope you keep solving problems by chunking them. Please leave a comment, correction or suggestion (I'd really love that). Thank you.