7
\$\begingroup\$

I want to check if a string contains only a single occurrence of the given substring (so the result of containsOnce("foo-and-boo", "oo") should be false). In Java, a simple and straightforward implementation would be either

boolean containsOnce(final String s, final CharSequence substring) {
    final String substring0 = substring.toString();
    final int i = s.indexOf(substring0);
    return i != -1 && i == s.lastIndexOf(substring0);
}

or

boolean containsOnce(final String s, final CharSequence substring) {
        final String substring0 = substring.toString();
        final int i = s.indexOf(substring0);
        if (i == -1) {
            return false;
        }

        final int nextIndexOf = s.indexOf(substring0, i + 1);
        return nextIndexOf == 0 || nextIndexOf == -1; // nextIndexOf is 0 if both arguments are empty strings.
}

Can you suggest a simpler/more efficient implementation?

\$\endgroup\$
  • \$\begingroup\$ Why do you assume the solution is not efficient? In your first solution you only scan the characters that are needed, which seems very efficient already? \$\endgroup\$ – RobAu Apr 21 '17 at 10:57
  • \$\begingroup\$ @RobAu In the first implementation you scan the string up till the end to search for a second occurence. If you search for oo in the string ooaooxxxxxxxxxxxxx....(huge string here) the second solution will only scan 2 + 3 letters. The first will scan the full huge string. I do agree that the second solution is efficient and readable enough though. \$\endgroup\$ – Imus Apr 21 '17 at 11:53
  • 1
    \$\begingroup\$ @Imus maybe I am missing something, but if the huge string is ooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoo the first solution will be faster as lastIndexOf() scans backwards? \$\endgroup\$ – RobAu Apr 21 '17 at 12:09
  • \$\begingroup\$ Aha, you are correct. ignore my previous comment :). Then it also comes down to preference on which is more readable, the first solution or my answer. \$\endgroup\$ – Imus Apr 21 '17 at 12:18
3
\$\begingroup\$

Perhaps using pattern matching. It looks more readable to me, but I have no idea about which is more efficient.

public static boolean containsOnce(final String s, final CharSequence substring) {
    Pattern pattern = Pattern.compile(substring.toString());
    Matcher matcher = pattern.matcher(s);
    if(matcher.find()){
        return !matcher.find();
    }
    return false;
}

public static void main(String[] args) throws Exception {
    System.out.println(containsOnce("aba","a"));    //false
    System.out.println(containsOnce("abab", "ab")); //false
    System.out.println(containsOnce("aba", "b"));   //true
    System.out.println(containsOnce("aaa", "aa"));  //true
    System.out.println(containsOnce("",""));        //true
    System.out.println(containsOnce("ab",""));      //false
}

Also note that containsOnce("aaa","aa") returns true. Not sure if you would count this as correct or not.

Note: you can also write it as

Pattern pattern = Pattern.compile(substring.toString());
Matcher matcher = pattern.matcher(s);
return matcher.find() && !matcher.find();

I don't know which of the two is more readable.

EDIT:

After looking up whichever is faster: indexof vs matcher
It seems to be the general consensus that indexof is a bit faster, but that we're talking about such low times that it really doesn't matter much.

Go for whichever solution you prefer I guess ...

\$\endgroup\$
0
\$\begingroup\$

I don't see anything wrong with the original post. Its concise and readable:

boolean containsOnce(String s, String sub) {
  int firstIndex = s.indexOf(sub)
  return firstIndex >=0 && firstIndex == s.lastIndexOf(sub)
}

I was writing a test recently that needed to verifying adding a string would not add if it existed (I used a set in the black box method) so I wrote something like this:

public void testNonDuplicateAdd() {
  String actual = methodUnderTest(stringToAdd, addingTo);
  assertThat(actual, containsString(stringToAdd));
  int firstIndex = actual.indexOf(stringToAdd);
  int lastIndex = actual.lastIndexOf(stringToAdd);
  assertThat(firstIndex, equals(lastIndex));
}
\$\endgroup\$
  • \$\begingroup\$ Do you mean return s.indexOf(substring) == s.lastIndexOf(substring);? Can you edit your post and add a little more explanation to why this works, for the sake of other readers? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 17 '18 at 19:14
  • \$\begingroup\$ This answer is useless. It suggests something which the first code sample in the question already does. Actually, this suggestion is inferior to the code sample in the question, because it does not account for the possibility that the substring is not contained at all. Have you even read the code in the question? \$\endgroup\$ – Stingy May 17 '18 at 21:01
-2
\$\begingroup\$

In terms of efficiency, the substring.toString() is the showstopper as soon as substring is not a java.lang.String. The rest of the code looks fine.

The documentation of the method should include containsOnce("fooo", "oo") as an example for returning false, since that might be a non-obvious corner case.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.