6

I read article with nice exercise about checking is string is a substring of another.

The content of the exercise is:

Write a program that takes 2 string parameters from the command line. Program must verify if the second string is a substring of the first string (you cannot use substr, substring or any other standard function including regular expression libraries).

Each occurrence of * in the second substring means that it can be a match for zero or more characters of the first string.

Consider the example: Input string 1: abcd Input string 2: a*c Program should evaluate that the string 2 is a substring of the string 1.

Additionally asterisk (*) may be considered as a regular character, if it is preceded by a backslash (\). Backslash (\) is considered as a regular character in all cases other than preceding the asterisk (*).

I wrote simple app, which firstly check that second string is NOT longer than first(but there is one problem, when test at ("ab", "a*b") this is correct test, but the method fails):

public static boolean checkCharactersCount(String firstString, String secondString) {
    return (firstString.length() > 0 && secondString.length() > 0) &&
            (firstString.length() > secondString.length());

... and next verify is a subtring:

public static boolean checkSubstring(String firstString, String secondString) {
    int correctCharCounter = 0;
    int lastCorrectCharAtIndex = -1;

    for (int i = 0; i < secondString.length(); i++) {
        for (int j = 0; j < firstString.length(); j++) {
            if (j > lastCorrectCharAtIndex) {

                if ((secondString.charAt(i) == firstString.charAt(j)) || secondString.charAt(i) == '*') {
                    correctCharCounter++;
                    lastCorrectCharAtIndex = j;
                }

                if (correctCharCounter >= secondString.length())
                    return true;
            }
        }
    }

    return false;
}

But there are two problems:

  1. My code as above does not support character continuity(for example test: checkSubstring("abacd", "bcd") return true, but it is wrong! - should return false)
  2. Any idea how to verify special symbol as "\*" ? Sample to test (checkSubstring("abc", "\b")

How is Your vision of solution? :)

Improve this question
8
  • 1
    Side note: the escaping rules are somewhat strange, they don't allow to specify a backslash followed by a wildcard. Commented Dec 10, 2018 at 12:21
  • @Henry Yep, hard to write it ;P We need to use double backslash("\\"), that define us second backslash ass real backlash or other sign :P Commented Dec 10, 2018 at 12:23
  • 1
    no, impossible. The meaning of \\* is a backslash (the first one) followed by a literal asterisk. Commented Dec 10, 2018 at 12:25
  • @Henry You're right :) Commented Dec 10, 2018 at 12:26
  • 2
    Note that your length check will rule out "ab" with "a*b", even though that should work, as the asterisk can stand for zero characters. Commented Dec 10, 2018 at 12:31

4 Answers 4

Reset to default
3

Try this: (Comments added for explanation)

// only for non empty Strings
public boolean isSubString(String string1,String string2)
{
    // step 1: split by *, but not by \*
    List<String>list1 = new ArrayList<String>();
    char[]cs = string2.toCharArray();
    int lastIndex = 0 ;
    char lastChar = 0 ;
    int i = 0 ;
    for(; i < cs.length ; ++i)
    {
        if(cs[i]=='*' && lastChar!='\\')
        {
            list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
            //earlier buggy line:
            //list1.add(new String(cs,lastIndex,i-lastIndex));
            lastIndex = i + 1 ;
        }
        lastChar = cs[i];
    }
    if(lastIndex < i )
    {
        list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
    }
    // step 2: check indices of each string in the list
    // Note: all indices should be in proper order.
    lastIndex = 0;
    for(String str : list1)
    {
        int newIndex = string1.indexOf(str,lastIndex);
        if(newIndex < 0)
        {
            return false;
        }
        lastIndex = newIndex+str.length();
    }
    return true;
}

in case you are not allowed to use String.indexOf() then write a function public int indexOf(String string1,String string2, int index2) and replace this statement

int newIndex = string1.indexOf(str,lastInxdex);

with this statement:

int newIndex = indexOf(string1, str,lastInxdex);

========================================================

Appendix A: The code i tested:

package jdk.conf;

import java.util.ArrayList;
import java.util.List;

public class Test01 {
    public static void main(String[] args)
    {
        Test01 test01 = new Test01();
        System.out.println(test01.isSubString("abcd", "a*c"));
        System.out.println(test01.isSubString("abcd", "bcd"));
        System.out.println(test01.isSubString("abcd", "*b"));
        System.out.println(test01.isSubString("abcd", "ac"));
        System.out.println(test01.isSubString("abcd", "bd"));
        System.out.println(test01.isSubString("abcd", "b*d"));
        System.out.println(test01.isSubString("abcd", "b\\*d"));
        System.out.println(test01.isSubString("abcd", "\\*d"));
        System.out.println(test01.isSubString("abcd", "b\\*"));

        System.out.println(test01.isSubString("a*cd", "\\*b"));
        System.out.println(test01.isSubString("", "b\\*"));
        System.out.println(test01.isSubString("abcd", ""));

        System.out.println(test01.isSubString("a*bd", "\\*b"));
    }
    // only for non empty Strings
    public boolean isSubString(String string1,String string2)
    {
        // step 1: split by *, but not by \*
        List<String>list1 = new ArrayList<String>();
        char[]cs = string2.toCharArray();
        int lastIndex = 0 ;
        char lastChar = 0 ;
        int i = 0 ;
        for(; i < cs.length ; ++i)
        {
            if(cs[i]=='*' && lastChar!='\\')
            {
                list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
                lastIndex = i + 1 ;
            }
            lastChar = cs[i];
        }
        if(lastIndex < i )
        {
            list1.add(new String(cs,lastIndex,i-lastIndex).replace("\\*", "*"));
        }
        // step 2: check indices of each string in the list
        // Note: all indices should be in proper order.
        lastIndex = 0;
        for(String str : list1)
        {
            int newIndex = string1.indexOf(str,lastIndex);
            if(newIndex < 0)
            {
                return false;
            }
            lastIndex = newIndex+str.length();
        }
        return true;
    }
}

Output:

true
true
true
false
false
true
false
false
false
false
false
true
true
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Check also if one of the input string is empty "", it will fail
How about ("a*bc", "\*b") ? Something is wrong, return false
@ACz ("a*bc", "*b") was not tried at all. Look again. Its ("a*cd", "\*b")
@ACz corrected the code. Now it will work for ("a*bc", "\*b")
Let us continue this discussion in chat.
1

I'd do this in a couple of stages.

Let's call the potential substring p and the string which we're testing for containing the substring s.

Break down the "contains" portion as a series of questions of "does p match starting at the Nth position of s?"; obviously you go through s from the first position onward to see if p matches at any position of s.

In matching, we have the possibility of running into a "*"; in that case, we want to know if the portion of p after the * is a substring of the portion of s after matching the portion of p up until the *. That suggests a recursive routine, taking the portion to be matched and the string to match and returning true/false. When you encounter a *, form the two new strings and call yourself.

If instead you encounter a \, then you just continue the regular matching with the next character instead of making the recursive call. Given that you need to do that, I suppose it might be easiest if you build pPrime from the original p, so that you can remove the backslash(es) when they're encountered, analagous to removing the asterisk(s) from the wildcard matching.

I haven't actually written any code on this, you only asked for approach.

Improve this answer

1 Comment

Nice vision of solution! The temporary string without backslash sounds good ;) I'm curious how you will solve it in the code
1

I found this a nice challenge to do. This exercise really forces us to think on a very low level of the language and algorithms in general. No lambdas, no streams, no regex, no find, no substring, nothing. Just the old CharAt, some fors and what not. Essentially I made a lookup method which looks up for the first character of the string to be found and then another lookup which takes into consideration your rules from that point onwards. If it fails, it goes back to the first index found, adds one and it does how many iterations necessary until the end of the string. If no match is found it's supposed to return false. If only one is found, then that is enough to consider it a substring. The most important corner cases are considered at the beginning of the calculus so that if false is detected as certain that it doesn't go further. Thus '*' alone means any character match and we can escape it with \. I tried to include most corner cases and this was really a challenge. I'm not entirely sure if my code covers all cases for you but it should cover quite a few. I really wanted to help you so this is my approach and here is my code:

package com.jesperancinha.string;

public class StringExercise {

    private static final char ASTERISK = '*';
    private static final char BACKSLASH = '\\';

    public boolean checkIsSubString(String mainString, String checkString) {
        int nextIndex = getNextIndex(0, checkString.charAt(0), mainString);
        if (nextIndex == -1) {
            return false;
        }
        boolean result = checkFromIndex(nextIndex, mainString, checkString);
        while (nextIndex < mainString.length() - 1 && nextIndex > -1) {
            if (!result) {
                nextIndex = getNextIndex(nextIndex + 1, checkString.charAt(0), mainString);
                if (nextIndex > -1) {
                    result = checkFromIndex(nextIndex, mainString, checkString);
                }
            } else {
                return result;
            }
        }
        return result;
    }

    private int getNextIndex(int start, char charAt, String mainString) {
        if (charAt == ASTERISK || charAt == BACKSLASH) {
            return start;
        }
        for (int i = start; i < mainString.length(); i++) {
            if (mainString.charAt(i) == charAt) {
                return i;
            }
        }
        return -1;
    }

    private boolean checkFromIndex(int nextIndex, String mainString, String checkString) {
        for (int i = 0, j = 0; i < checkString.length(); i++, j++) {
            if (i < (checkString.length() - 2) && checkString.charAt(i) == BACKSLASH
                    && checkString.charAt(i + 1) == ASTERISK) {
                i++;
                if (mainString.charAt(j + nextIndex) == BACKSLASH) {
                    j++;
                }
                if (checkString.charAt(i) != mainString.charAt(j + nextIndex)) {
                    return false;
                }
            }
            if (i > 0 && checkString.charAt(i - 1) != BACKSLASH
                    && checkString.charAt(i) == ASTERISK) {
                if (i < checkString.length() - 1 && (j + nextIndex) < (mainString.length() - 1)
                        && checkString.charAt(i + 1) !=
                        mainString.charAt(j + nextIndex + 1)) {
                    i--;
                } else {
                    if (j + nextIndex == mainString.length() - 1
                            && checkString.charAt(checkString.length() - 1) != ASTERISK
                            && checkString.charAt(checkString.length() - 2) != BACKSLASH) {
                        return false;
                    }
                }
            } else {
                if ((j + nextIndex) < (mainString.length() - 2) &&
                        mainString.charAt(j + nextIndex)
                                != checkString.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }

}

I have made a set of unit tests but if I would put the whole class here it would be too long and the only thing I want to show you is the test cases I implemented in the unit tests. Here is the condensed version of my unit tests for this case:

package com.jesperancinha.string;

import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.Test;

class StringExerciseMegaTest {

    @Test
    void checkIsSubString() {
        StringExercise stringExercise = new StringExercise();
        boolean test = stringExercise.checkIsSubString("abcd", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "a\\*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("a*c", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*c", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*csdfdsfdsfdsf", "a\\*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa**csdfdsfdsfdsf", "a\\*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("aasdsadasa**csdfdsfdsfdsf", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdsadasa*csdfdsfdsfdsf", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "a*c");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "dwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriouiauoisdf9977675tyhfgh", "75tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\iauoisdf9977675tyhfgh", "riou\\iauois");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9977675tyhfgh", "riou\\\\*iauois");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\\\*977675tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\*977675tyhfgh");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("\\*aasdweriou\\*iauoisdf9\\*977675tyhfgh", "\\*aasdwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("*aasdweriou\\*iauoisdf9\\*977675tyhfgh", "*aasdwer");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "bc");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "zbc");
        assertThat(test).isFalse();
        test = stringExercise.checkIsSubString("abcd", "*bc*");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("*bcd", "\\*bc*");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "a*c");
        assertThat(test).isTrue();
        test = stringExercise.checkIsSubString("abcd", "az*bc");
        assertThat(test).isFalse();
    }
}
Improve this answer

2 Comments

Awesome answer! Yea is it nice challange, there are a lot of cases to check as empty string, no sign, count of chars, special chars etc... The exercise looks really easy but if we start coding, we can see that there is so many cases and if statements which wee need to check ;D Give me a while to check this code, it looks so complicated
@ACz, Thanks! glad to help!
0

My Solution looks like this, i commented everything so hopefully you can understand this. 

public static void main(String [] args) throws Exception {
        System.err.println(contains("bruderMusssLos".toCharArray(),"Mu*L*".toCharArray()));
}

public static boolean contains(char [] a, char [] b) {

    int counterB = 0; // correct characters
    char lastChar = '-'; //last Character encountered in B

    for(int i = 0; i < a.length; i++) {

        //if last character * it can be 0 to infinite characters
        if(lastChar == '*') {

            //if next characters in a is next in b reset last char
            // this will be true as long the next a is not the next b
            if(a[i] == b[counterB]) {
                lastChar = b[counterB];
                counterB++;

            }else {
                counterB++;
            }

        }else {

            //if next char is * and lastchar is not \ count infinite to next hit
            //otherwise * is normal character
            if(b[counterB] == '*' && lastChar != '\\') {
                lastChar = '*';
                counterB++;
            }else {
                //if next a is next b count
                if(a[i] == b[counterB]) {
                    lastChar = b[counterB];
                    counterB++;
                }else {
                    //otherwise set counter to 0
                    counterB = 0;
                }                   
            }

        }

        //if counterB == length a contains b
        if(counterB == b.length)
            return true;

    }


    return false;
}

Current test is returning true for example :)

Improve this answer

2 Comments

Ok i realised it's not working for * = 0 Characters, my bad. So there would be a extra check up for that, but besides that this is working for everything * > 0 characters, and arrays.length > 0.
let me check, I will bring back a answer back

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.