4
\$\begingroup\$

I wrote the following code in response to this question "find sum of number of times that each character of source occurs in the target", is there any better solution for it?

Analysis

Target is alex alexander    
Source is ardx
Characters of source that exist in target are like a--x-a--xa-d-r 
Total is 7.

Code

    String target = "alex alexander";
    String source = "ardx";
    char[] a = source.toCharArray();
    int occurrences = 0;

    for (int i = 0; i < a.length; i++) {
        String t = target;
        int index = t.indexOf(a[i]);

        while (index != -1) {
            occurrences++;
            t = t.substring(index + 1);
            index = t.indexOf(a[i]);
        }

    }
    System.out.println(occurrences);
}

Output

7
\$\endgroup\$
  • \$\begingroup\$ You could turn the logic around and check how many characters of target occur in source \$\endgroup\$ – Jack Sep 17 '14 at 0:38
  • \$\begingroup\$ Posted a follow-on question: Shady Characters \$\endgroup\$ – rolfl Sep 17 '14 at 2:10
  • \$\begingroup\$ Please find the follow up to this question here codereview.stackexchange.com/questions/63107/… \$\endgroup\$ – Jack Sep 17 '14 at 4:36
5
\$\begingroup\$

Your code is neat, well structured, and generally very readable. People solving this problem are often beginners, and your code, for a beginner, is good.

My only style complaint is the use of a for the array variable name.

Your algorithm is technically a nested loop. You loop through each character in the source, and for each of the source characters, you loop through the characters in target.

Note that the indexOf function is essentially a loop, it starts at the start index, and loops until it gets to the end, or the character. Your while loop is just a way to 'pause' the loop at significant places.

So, your algorithm will scan the target one time for each source character. Each time there is a match, you increment the occurrences.

Your algorithm could be made more apparent if you were to make the inner loop more obvious:

for (int j = 0; j < target.length(), j++) {
    if (target.charAt(j) == a[i]) {
        occurrences++;
    }
}

That makes the logic more visible, and removes the call to indexOf....

Obviously, it would help to convert the target to a char array outside the loop:

char[] tchars = target.toCharArray();

and then the inner loop would be:

for (int j = 0; j < tchars.length, j++) {
    if (tchars[j] == a[i]) {
        occurrences++;
    }
}

There is a potential bug with your solution.... if a character is duplicated in the source, you will double-count it in the result.

You will want to deal with that.

There is also a possibly more efficient algorithm which would be useful for large strings, but, with anything less than say 100 chars, I would not bother. That algorithm would require setting up a HashMap or other data structure from the source chars, and then just looping once through the target chars to get the counts.

\$\endgroup\$
  • \$\begingroup\$ thanks, would you please provide me with a better algorithm, I need to compare that with mine to learn more. \$\endgroup\$ – Jack Sep 16 '14 at 22:28
  • 2
    \$\begingroup\$ @Jack This answer should have given you a good starting point for how to improve your code. Reviewers have no obligation to provide you with the final result, I suggest that you spend some time reading and understanding the answer and trying to make your code better. It is, after all, your code, not rolfl's. \$\endgroup\$ – Simon Forsberg Sep 16 '14 at 22:40
  • \$\begingroup\$ @SimonAndréForsberg ok, once I changed my code, should I update the question or post a new one? \$\endgroup\$ – Jack Sep 16 '14 at 22:53
  • \$\begingroup\$ @Jack You should post a follow-up question. Just make sure that the code is working if you post it on Code Review. If you are having problems getting the new code to work, I suggest that you ask on Stack Overflow \$\endgroup\$ – Simon Forsberg Sep 16 '14 at 22:54
  • 1
    \$\begingroup\$ @Jack , see this: What you can and cannot do after receiving answers \$\endgroup\$ – rolfl Sep 16 '14 at 22:55
5
\$\begingroup\$

As already stated, the code is fine. Just a few comments:

t = t.substring(index + 1);
index = t.indexOf(a[i]);

Learn the libraries, use

index = t.indexOf(a[i], lastIndex+1);

instead of generating new strings again and again.


There's a much faster way, but speed usually doesn't matter. Ignore tiny speed ups as Premature optimization is the root of all evil. OTOH linear time instead of quadratic is a nice thing.

You could use a Set<Character> to remember what chars occur in the first string. Using the fact that the possible set of characters is limited (by \$2^{16}\$), you could use a boolean[] instead.


I see you're asking for a better algorithm, but I've just invented a much shorter one instead.

byte[] charsInSource = new byte[Character.MAX_VALUE + 1];
for (int i = 0; i < a.length; i++) charsInSource[source.charAt(i)] = 1;
for (int i = 0; i < a.length; i++) result += charsInSource[target.charAt(i)]

This array is surely long enough. Java guarantees that it gets initialized to all zeros. It gets used to map each source char to 1 and all others to 0.

\$\endgroup\$
  • \$\begingroup\$ I do not also get what you mean by using boolean[] \$\endgroup\$ – Jack Sep 16 '14 at 22:35
  • \$\begingroup\$ thanks, whats your idea about rolfl's answer? he claims there is a professional solution for this question. \$\endgroup\$ – Jack Sep 16 '14 at 22:37
  • \$\begingroup\$ hmm I missed the substring... good catch, how embarrassing for me. \$\endgroup\$ – rolfl Sep 16 '14 at 22:42
  • \$\begingroup\$ @Jack If he says it, you should believe it. My solution is hacky... and allocates "a lot" of memory. The boolean[] would be indexed by the character (just like my byte[] is). Imagine allocating one slot for each character, you store there if it occurs in source. \$\endgroup\$ – maaartinus Sep 16 '14 at 22:45
  • \$\begingroup\$ please find the follw-up question here codereview.stackexchange.com/questions/63107/… \$\endgroup\$ – Jack Sep 17 '14 at 4:36

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.