String Fragment Combinations Puzzle

Question

Let's say I am given a list of String fragments. Two fragments can be concatenated on their overlapping substrings.

e.g.

"sad" and "den" = "saden"

"fat" and "cat" = cannot be combined.

Sample input:

aw was poq qo

Sample output:

awas poqo

So, what's the best way to write a method which find the longest string that can be made by combining the strings in a list. If the string is infinite the output should be "infinite".

public class StringUtil {

    public static String combine(List<String> fragments) {
        StringBuilder combined = new StringBuilder();
        for (int i = 0; i < fragments.size(); i++) {
            char last = (char) (fragments.get(i).length() - 1);
            if (Character.toString(last).equals(fragments.get(i).substring(0))) {
                combined.append(fragments.get(i)).append(fragments.get(i+1));
            }
        }
        return combined.toString();
    }
}

Here's my JUnit test:

public class StringUtilTest {

    @Test
    public void combine() {
        List<String> fragments = new ArrayList<String>();
        fragments.add("aw");
        fragments.add("was");
        fragments.add("poq");
        fragments.add("qo");
        String result = StringUtil.combine(fragments);
        assertEquals("awas poqo", result);
    }
}

This code doesn't seem to be working on my end... It returning an empty string:

org.junit.ComparisonFailure: expected:<[awas poqo]> but was:<[]>

How can I get this to work? And also how can I get it to check for infinite strings?

possible duplicate of [Efficient Algorithm for String Concatenation with Overlap](http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap) — Evan Knowles, Jun 19 '15 at 05:25
Your requirement is unclear, and it may just be a typo, but how does `inquisit` and `tision` make `inquisition`? Also, how can combining any number of strings in a list give an infinite result? — Dawood ibn Kareem, Jun 19 '15 at 05:26
@David Wallace, the pattern is that if the last letter of an item matches the the first letter of the subsequent item than to combine together. — PacificNW_Lover, Jun 19 '15 at 05:31
By that rule, `inquisit` and `tision` would make `inquisitision`. Is that what you meant to have? — Dawood ibn Kareem, Jun 19 '15 at 05:32
And the best way to check for infinite strings is only to run your program on a computer with a finite amount of memory. :-) — Dawood ibn Kareem, Jun 19 '15 at 05:33
@Jens, yes... but I can't seem to make it work. By the way, its not a duplicate to the efficient algorithm, because if it was then "fat" and "cat" would be able to be combined. — PacificNW_Lover, Jun 19 '15 at 05:37
@socal_javaguy Try clarifying your requirement first. Then somebody might be able to help you. Right now, all we can really do is guess what your question means. — Dawood ibn Kareem, Jun 19 '15 at 05:38
@socal_javaguy can you add a runable example, so that we can copy and run the program by our own? — Jens, Jun 19 '15 at 05:38
@Jens. I don't know how to fix this puzzle that's why I posted a question. Thanks. — PacificNW_Lover, Jun 19 '15 at 05:40
@socal_javaguy Bu yu can run your program to see that is not working? — Jens, Jun 19 '15 at 05:40
And now it's even more confusing. Why is `sad + den = sadden` but `aw + was = awas`? Do we double the joining letter or not? And can you give an example of a case where the answer would be what you called infinite? — Dawood ibn Kareem, Jun 19 '15 at 05:49
@David Wallace, you are correct, it should be "sad + den" = "saden". Let me fix that in the problem description. — PacificNW_Lover, Jun 19 '15 at 05:51

Ron Thompson · Answer 1 · 2015-06-19T06:17:14.090

I don't understand how fragments.get(i).length() - 1 is supposed to be a char. You clearly casted it on purpose, but I can't for the life of me tell what that purpose is. A string of length < 63 will be converted to an ASCII (Unicode?) character that isn't a letter.

I'm thinking you meant to compare the last character in one fragment to the first character in another, but I don't think that's what that code is doing.

My helpful answer is to undo some of the method chaining (function().otherFunction()), store the results in temporary variables, and step through it with a debugger. Break the problem down into small steps that you understand and verify the code is doing what you think it SHOULD be doing at each step. Once it works, then go back to chaining.

Edit: ok I'm bored and I like teaching. This smells like homework so I won't give you any code.

1) method chaining is just convenience. You could (and should) do:

String tempString = fragments.get(i);

int lengthOfString = tempString.length() - 1;

char lastChar = (char) lengthOfString;//WRONG

Etc. This lets you SEE the intermediate steps, and THINK about what you are doing. You are literally taking the length of a string, say 3, and converting that Integer to a Char. You really want the last character in the string. When you don't use method chaining, you are forced to declare a Type of intermediate variable, which of course forces you to think about what the method ACTUALLY RETURNS. And this is why I told you to forgo method chaining until you are familiar with the functions.

2) I'm guessing at the point you wrote the function, the compiler complained that it couldn't implicitly cast to char from int. You then explicitly cast to a char to get it to shut up and compile. And now you are trying to figure out why it's failing at run time. The lesson is to listen to the compiler while you are learning. If it's complaining, you're messing something up.

3) I knew there was something else. Debugging. If you want to code, you'll need to learn how to do this. Most IDE's will give you an option to set a break point. Learn how to use this feature and "step through" your code line by line. THINK about exactly what step you are doing. Write down the algorithm for a short two letter pair, and execute it by hand on paper, one step at a time. Then look at what the code DOES, step by step, until you see somewhere it does something that you don't think is right. Finally, fix the section that isn't giving you the desired result.

I need to chain it because how else would I compare if it was 4 elements instead of two? You are right about what I am trying to do "... compare the last character in one fragment to the first character in another, but I don't think that's what that code is doing." — PacificNW_Lover, Jun 19 '15 at 05:46
Ron, I know how to use the debugger, I just used method chaining because I couldn't figure out how to have it compare each item. This isn't homework. Its just a puzzle that I am trying to ambitiously solve. Sorry, if you were perturbed by the way I asked the question. — PacificNW_Lover, Jun 19 '15 at 06:29
@socal_javaguy: I'm terribly not offended at all. If it's not homework, I apologize. I see it a lot. Still, the rest of the answer holds :). I'd rather teach a man to fish. — Ron Thompson, Jun 19 '15 at 06:34
Ron Thompson... I was posting to see how others would go about solving it. I had initially had used the for each as Abishek suggested but was confused. Thanks for the apology. — PacificNW_Lover, Jun 19 '15 at 06:36

Codebender · Answer 2 · 2015-06-19T06:30:17.690

0

Looking at your unit test, the answer seems to be quite simple.

public static String combine(List<String> fragments) {
    StringBuilder combined = new StringBuilder();
    for (String fragment : fragments) {
        if (combined.length() == 0) {
            combined.append(fragment);
        } else if (combined.charAt(combined.length() - 1) == fragment.charAt(0)) {
            combined.append(fragment.substring(1));
        } else {
            combined.append(" " + fragment);
        }
    }
    return combined.toString();
}

But seeing at your inqusition example, you might be looking for something like this,

public static String combine(List<String> fragments) {
    StringBuilder combined = new StringBuilder();
    for (String fragment : fragments) {
        if (combined.length() == 0) {
            combined.append(fragment);
        } else if (combined.charAt(combined.length() - 1) == fragment.charAt(0)) {
            int i = 1;
            while (i < fragment.length() && i < combined.length() && combined.charAt(combined.length() - i - 1) == fragment.charAt(i))
                i++;
            combined.append(fragment.substring(i));
        } else {
            combined.append(" " + fragment);
        }
    }
    return combined.toString();
}

But note that for your test, it will generate aws poq which seems to be logical.

edited Jun 19 '15 at 06:30

answered Jun 19 '15 at 06:16

Codebender

14,221
7
48
85

Thanks Abishek! However, the unit test failed org.junit.ComparisonFailure: expected: but was: – PacificNW_Lover Jun 19 '15 at 06:23
Did you use the same code as the answer? Because it has a in between different words. – Codebender Jun 19 '15 at 06:25
Yes, I copied and pasted your code and it gave me that comparison failure. – PacificNW_Lover Jun 19 '15 at 06:28
Still doesn't work: org.junit.ComparisonFailure: expected: but was: It supposed to be "awas poqo" not "aws poq". – PacificNW_Lover Jun 19 '15 at 06:33
The first code will give awas poqo... But for "inquisit" and "tision" it will be "inquisitision" and not "inquisiton". – Codebender Jun 19 '15 at 06:46
Its supposed to work for awas poqo... Inquisition was a bad example and I am removing it from the problem description. The first code still doesn't work. I guess I stumbled upon a puzzle that is unsolvable. – PacificNW_Lover Jun 19 '15 at 06:49

String Fragment Combinations Puzzle

2 Answers2