CODEWITHSUNDEEP
javaalgorithmstring
Matey
Matey

Reputation: 107

Determine if a string can be transformed to another string when only insert/remove/replace operations are allowed

I must write a function that takes two words (strings) as arguments, and determines if the first word can be transformed into the second word using only one first-order transformation.

Any suggestions? Any Java examples would be great!

Upvotes: 3

Views: 1068

Answers (4)

polygenelubricants
polygenelubricants

Reputation: 383876

If you need to check if there is one and exactly one edit from s1 to s2, then this is very easy to check with a simple linear scan.

  • If both have the same length, then there must be exactly one index where the two differ
    • They must agree up to a common longest prefix, then skipping exactly one character from both, they must then agree on a common suffix
  • If one is shorter than the other, then the difference in length must be exactly one
    • They must agree up to a common longest prefix, then skipping exactly one character from the longer one, they must then agree on a common suffix

If you also allow zero edit from s1 to s2, then simply check if they're equal.

Here's a Java implementation:

static int firstDifference(String s1, String s2, int L) {
    for (int i = 0; i < L; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            return i;
        }
    }
    return L;
}
static boolean oneEdit(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return oneEdit(s2, s1);
    }
    final int L = s1.length();
    final int index = firstDifference(s1, s2, L);
    if (s1.length() == s2.length() && index != L) {
        return s1.substring(index+1).equals(s2.substring(index+1));
    } else if (s2.length() == L + 1) {
        return s1.substring(index).equals(s2.substring(index+1));
    } else {
        return false;
    }
}

Then we can test it as follows:

    String[][] tests = {
        { "1", "" },
        { "123", "" },
        { "this", "that" },
        { "tit", "tat" },
        { "word", "sword" },
        { "desert", "dessert" },
        { "lulz", "lul" },
        { "same", "same" },
    };
    for (String[] test : tests) {
        System.out.printf("[%s|%s] = %s%n",
            test[0], test[1], oneEdit(test[0], test[1])
        );
    }

This prints (as seen on ideone.com):

[1|] = true
[123|] = false
[this|that] = false
[tit|tat] = true
[word|sword] = true
[desert|dessert] = true
[lulz|lul] = true
[same|same] = false

Upvotes: 1

dcp
dcp

Reputation: 55458

This does look like homework so I'm not going to give you the answer, but any time you approach a problem like this the best thing to do is start sketching out some ideas. Break the problem down into smaller chunks, and then it becomes easier to solve.

For example, let's look at the insert operation. To insert an letter, what is that going to do to the length of the word in which we are inserting the letter? Increase it or decrease it? If we increase the length of the word, and the length of this new word is not equal to the length of the word we are trying to match, then what does that tell you? So one condition here is that if you are going to perform an insert operation on the first word to make it match the second word, then there is a known length that the first word must be.

You can apply similar ideas to the other 2 operations.

So once you establish these conditions, it becomes easier to develop an algorithm to solve the problem.

The important thing in any type of assignment like this is to think through it. Don't just ask somebody, "give me the code", you learn nothing like that. When you get stuck, it's ok to ask for help (but show us what you've done so far), but the purpose of homework is to learn.

Upvotes: 2

Carl Smotricz
Carl Smotricz

Reputation: 67790

Think: If you're only allowed a single transformation, then the difference in length between the "before" and "after" words should give you a very strong hint as to which of those three transformations has any chance of being successful. By the same token, you can tell at a glance which transformations will be simply impossible.

Once you've decided on which transformation, the rest of the problem becomes a job for Brute Force Man and his sidekick, Looping Lady.

Upvotes: 5

InsertNickHere
InsertNickHere

Reputation: 3666

You can use the Levenshtein distance and only allow distances of 1 (which means, one char must be altered). There are several implementations just google "Levenshtein java" or so.

The other "not so smart" but working thing would be the good old brute force. Just try out every situation with every char and you get what you want. :-)

Upvotes: 1

Related Questions