Son of a....

[Maximilian]

Spent the better part of an hour trying to solve what seemed like a simple problem, its labelled as a hard problem but it didnt look all that tough:

Given two strings, base and remove, return a version of the base string where all instances of the remove string have been removed (not case sensitive). You may assume that the remove string is length 1 or more. Remove only non-overlapping instances, so with "xxx" removing "xx" leaves "x".

withoutString("Hello there", "llo") → "He there"
withoutString("Hello there", "e") → "Hllo thr"
withoutString("Hello there", "x") → "Hello there"

100 lines of code later and i still haven't got it :| Then i look at Strings methods and see a wonderful little method called replaceAll() 😡

base = base.replaceAll(remove, "");
//does basically what my 100 lines and while loops with lists arrays and the whole shebang failed to do.

Felt like sharing :awe:

 

[Ken g6]

Isn't replaceAll case sensitive, though?

 

[Maximilian]

Yeah i just did this:

public String withoutString(String base, String remove) 
{
   String output = new String(base);
   
   //replace exact occurances of string
   output = output.replaceAll(remove, "");

   //replace lower case occurrences of string
   output = output.replaceAll(remove.toLowerCase(), "");
   
   //replace upper case occurrences of string
   output = output.replaceAll(remove.toUpperCase(), "");

   return output;
}

I had a look at the java code for the replaceall() method, just to see how they did it. It uses class Pattern and class Match and Match's replaceall() which uses a bunch of other methods... looks complex as hell.

No wonder i failed trying to do it manually lol.

 

[tfinch2]

If this is homework, your professor probably does not want you to use replaceAll, or any String class methods to solve this problem.

 

[Maximilian]

If this is homework, your professor probably does not want you to use replaceAll, or any String class methods to solve this problem.

Nah its from these problems someone linked in the other thread:

http://codingbat.com/java

Without those methods i was probably ~75% of the way there. I had identified where all occurrences of remove occurred in base i just had no way to create an output string. As soon as i delete the first occurrence of remove from say a StringBuilder object its index values will change so my occurrences of remove would no longer be valid then removing everything after that would fail. I messed about with some kind of index offset to solve this but couldn't make it work.

Perhaps if i had used a fixed Array of chars for the output object instead of a StringBuilder... then converted the array to a String for output :hmm: Might be easier that way since the Array wont shrink when i take stuff out.

 

[ikachu]

Hm unless I'm having a brain fart I don't think your code will work if the base string contains the remove string but the case is mixed... so for example:

withoutString("HeLLo there", "llo") won't match 'llo' or 'LLO'

 

[BrightCandle]

Hm unless I'm having a brain fart I don't think your code will work if the base string contains the remove string but the case is mixed... so for example:

withoutString("HeLLo there", "llo") won't match 'llo' or 'LLO'

Your absolutely right it does not. A simple xXx for matching against xx will be sufficient to break the solution given.

To do this efficiently takes a bit more work but nievely the algorithm is quite simple.

You loop character by character of the string and match against the first character (in this case ignoring case). Then when it matches you check the other characters and if they all match you remove the text from the original string and use the new string with parts removed and the current index into it and carry on until you reach the end. Its most easily done with recursion but you don't have tail recursion in Java which means its limited to around 1000 replacements.

 

[Pia]

One very easy way to write this is figuring out how to remove the first matched string, making a function for that which returns true if a removal happened, and:

removeAll(base, remove) {
    while (removeOne(base, remove))
        ;
    return base;
}

 

[beginner99]

Your absolutely right it does not. A simple xXx for matching against xx will be sufficient to break the solution given.

To do this efficiently takes a bit more work but nievely the algorithm is quite simple.

You loop character by character of the string and match against the first character (in this case ignoring case). Then when it matches you check the other characters and if they all match you remove the text from the original string and use the new string with parts removed and the current index into it and carry on until you reach the end. Its most easily done with recursion but you don't have tail recursion in Java which means its limited to around 1000 replacements.

java string.replaceAll() takes a regex. To make it case-insenstive use (?i) at start of regex.

String target = "FOOBar";
target = target.replaceAll("(?i)foo", "");

And this is why I always google for stuff like this (if I don't know it) because it seems obvious someone will already have had the same problem.

 

[Maximilian]

Hm unless I'm having a brain fart I don't think your code will work if the base string contains the remove string but the case is mixed... so for example:

withoutString("HeLLo there", "llo") won't match 'llo' or 'LLO'

Hmm yeah you're right it wont do that. It will pass the tests thrown at it though:

http://codingbat.com/prob/p192570

One very easy way to write this is figuring out how to remove the first matched string, making a function for that which returns true if a removal happened, and:

removeAll(base, remove) {
    while (removeOne(base, remove))
        ;
    return base;
}

Wow, that looks extremely promising! Gonna give that a shot later.

 

[Maximilian]

I tried recursion but eventually nailed it in one method, seems to work:

    public static String removeAll(String base, String remove)
    {
        //boolean removed = false;
        char[] baseArray = base.toCharArray();
        
        //create character list of base
        List<Character> baseList = new ArrayList<>();
        for (char aChar : baseArray)
        {
            baseList.add(aChar);
        }
        
        //create character list of remove
        char[] removeArray = remove.toCharArray();
        List<Character> removeList = new ArrayList<>();
        for (char aChar : removeArray)
        {
            removeList.add(aChar);
        }
        
        //start and end index of current check
        int currentStartIndex = 0;
        int currentEndIndex = remove.length()-1;
        
        //index of currently checked character
        int currentCheckPosition = 0;
        
        //amount of letter matches so far regardless of case
        int letterMatches = 0;
        
        //current index of removeList to be checked against, e.g if the character at
        //index 0 is a match then the next character is checked at index 1 etc
        int removeCharacterCheckIndex = 0;
        
        //must know if there was a removal as the List will shrink and indexs will change
        //as a result
        boolean hadRemoval = false;
        
        //while still within the bounds of baseList
        while (currentEndIndex <= baseList.size()-1)
        {
            System.out.println("outer loop");
            currentCheckPosition = currentStartIndex;
            
            //while we have not reached the end of the current check
            while (currentCheckPosition <= currentEndIndex)
            {
                hadRemoval = false;
                //get current character
                String currentBaseCharacterCheck = baseList.get(currentCheckPosition).toString();
                
                //get current character to check against
                String currentRemoveCharacterCheck = removeList.get(removeCharacterCheckIndex).toString();
                
                //if current character matches check character
                if (currentBaseCharacterCheck.equals(currentRemoveCharacterCheck))
                {
                    letterMatches++;
                    removeCharacterCheckIndex++;
                }
                else
                {
                    //if current character matches upper case version of check character
                    if (currentBaseCharacterCheck.toUpperCase().equals(currentRemoveCharacterCheck))
                    {
                        letterMatches++;
                        removeCharacterCheckIndex++;
                    }
                    else
                    {
                        //if current character matches lower case version of check character
                        if (currentBaseCharacterCheck.toLowerCase().equals(currentRemoveCharacterCheck))
                        {
                               letterMatches++;
                               removeCharacterCheckIndex++;
                        }
                    }
                }
                
                //if we have the correct amount of matches, we remove the charatcers
                if (letterMatches == remove.length())
                {
                    for (int count = 0; count < remove.length(); count++)
                    {
                        baseList.remove(currentStartIndex);
                    }
                    
                    //reset the indexs to accommodate for baseList shrinking in size
                    // after removal of characters
                    currentStartIndex = 0;
                    currentEndIndex = remove.length()-1;
                    hadRemoval = true;
                }
                
                currentCheckPosition++;
            }
            
            //no incrementation if a removal took place this loop
            if (!hadRemoval)
            {
                currentStartIndex++;
                currentEndIndex++;
            }

            removeCharacterCheckIndex = 0;
            letterMatches = 0;
        }
        
        //turn resulting baseList into StringBuilder, then into String for output
        StringBuilder outputStringBuilder = new StringBuilder();
        for (Character aChar : baseList)
        {
            outputStringBuilder.append(aChar);
        }
        
        String output = outputStringBuilder.toString();
        
        return output;
    }

I tried it with the line:

System.out.println(removeAll("hellolloLloLLollOcucumberballo chicken soup","llo"));

and it removed all occurrences! Huzzah :awe:

 

[beginner99]

I tried recursion but eventually nailed it in one method, seems to work:

and it removed all occurrences! Huzzah :awe:

grats but again replaceAll would have been much easier:

@Test
public void testReplace() {
    String result = "hellolloLloLLollOcucumberballo chicken soup".replaceAll("(?i)llo", "");
    assertEquals("hecucumberba chicken soup", result);
}

 

[Maximilian]

grats but again replaceAll would have been much easier:

@Test
public void testReplace() {
    String result = "hellolloLloLLollOcucumberballo chicken soup".replaceAll("(?i)llo", "");
    assertEquals("hecucumberba chicken soup", result);
}

Yeah i tried that out before i took the DIY method, I kept putting (?!) instead of (?i) though heh, reading fail, worked great when i realized what id done. Still... wondered if i could do it myself anyway.