Recursive Contains Method

Question

The method below recursively checks if a string contains another string. Example: contains(hello, lo, 0) should return true, while contains(hello, eh, 0) should return false. The method itself works, but I was wondering how it could be made more efficient/generally better.

Method:

public static boolean contains(String word1, String word2, int index)
{   
    if((word1 == null) || (word2 == null)){
        return false; 
    }

    if(index + (word2.length() - 1) >= word1.length()){
        return false; 
    } 

    int count = 0, j = 0;

    for(int i = index; i < (word2.length() + index); i++){ 
        if(word1.charAt(i) == word2.charAt(j)){
            if((i != 0) && (j != 0)){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    count++;
                }  
            } else {
                count++;
            }
        }
        j++;
    } 

    if(count == word2.length()){
        return true; 
    } 

    return contains(word1, word2, index + 1);
}

neilk · Accepted Answer · 2017-02-16 18:24:29Z

2

For proper recursive 'style', you shouldn't use a for-loop inside the function. Each pass through the function should perform one test and then set up the next pass. This also frees you from needing to track the index as an argument.

Consider that:

contains("hello", "lo") == 
contains("ello", "lo") == 
contains("llo", "lo") == 
contains("lo", "lo")

answered Feb 16, 2017 at 18:24

neilk

213 bronze badges

Add a comment |

oopexpert · Accepted Answer · 2017-02-16 16:59:01Z

1

No null checks

You should not check for null input values. Semantically you cannot dermine a proper return value. So if at least one parameter is null returning true would be as valid as return false even false will often be more beneficial. So the return value will be more or less a convention than a correct answer.

My suggestion is to not expect null as a parameter. You method signature says "give me a String" so the caller has to give you a String. This is the least the caller should do passing a value of the propert type as null can be of ANY type as seen here:

String s = null;
Object o = o;
Integer i = (Integer) o;

Avoid multiple return statements

Try to reformulate your algorithm so you have only one return statement at the end.

The problem is that the constructs like break, continue and multiple return are not refactoring-friendly. Extracting methods out of the current method that contains such constructs will lead to reformulating your whole control flow.

Naming

Try to rename i, j, count and index to match there semantic best. (e.g. startIndex, offset, word2Index, ...)

answered Feb 16, 2017 at 16:59

oopexpert

3,18211 silver badges17 bronze badges

\$\begingroup\$ To expand on the "no nulls" part, I'd like to point out that javaee holds a validation framework nowadays, where you can declare a parameter as "@NotNull". Furthermore, to enforce this, we have the utility method Objects.requireNonNull() since java 8. In combination, this serves for the IDE/compiler to do static null analysis and enforces a NullPointerException for runtime violations. \$\endgroup\$

mtj
– mtj

2017-02-17 10:33:28 +00:00
Commented Feb 17, 2017 at 10:33
\$\begingroup\$ I know Objects.requireNonNull() and of course NotNull annotations. I consider Objects.requireNonNull() as boiler-plate code as described in my answer. But if NotNull at a parameter will force the caller at compile time to pass an object of the proper type then I am interested in this configuration. Otherwise NotNull may "fail fast". But furthermore it is only a nice hint that developers should follow anyway: Never pass null as a parameter, never return null where it is inappropriate. \$\endgroup\$

oopexpert
– oopexpert

2017-02-17 10:49:07 +00:00
Commented Feb 17, 2017 at 10:49
\$\begingroup\$ Another point that is the most important but less considered: Psychology. Null checks are inflationary. If one method checks for null other methods tend to do this as well. In the past I saw null checks in one method that exceeds a ratio from 3 to 1 regarding the "productive code" intention of the method. Using null checks is a message to other developers that they might expect null in other cases so they will continue to pollute their code with null checks. With null checks you build in a basic uncertainty and other developer will have various nonsensical answers to it. \$\endgroup\$

oopexpert
– oopexpert

2017-02-17 12:57:47 +00:00
Commented Feb 17, 2017 at 12:57
\$\begingroup\$ 100% aggree. That's why I recommend @NotNull, also on return types. That way, the "other developer" using a function at least gets a warning about useless null checks. (Time to switch the severity level to "error" ;-)) \$\endgroup\$

mtj
– mtj

2017-02-18 06:37:38 +00:00
Commented Feb 18, 2017 at 6:37

Add a comment |

Stack Exchange Network

Recursive Contains Method

2 Answers 2

No null checks

Avoid multiple return statements

Naming

You must log in to answer this question.

Hot Network Questions

Recursive Contains Method

2 Answers 2

No null checks

Avoid multiple return statements

Naming

You must log in to answer this question.

Related

Hot Network Questions