Kurt Bauer

Posted on Mar 18, 2020

CodeToday: "Word Split" Algorithm, Coderbyte

#javascript #algorithms #motivation #todayilearned

The Gist

I had worked on a Medium level Coderbyte challenge for an interview, but was unable to make any decent headway at the time. So I did what any reasonable person would do, let it bother me to the point that I made a codepen just to solve it.

The Problem

Problem: Have the function WordSplit(strArr) read the array of strings stored in strArr, which will contain 2 elements: the first element will be a sequence of characters, and the second element will be a long string of comma-seperated words, in alphabetical order, that represents a dictionary of some arbitrary length. For example: strArr can be: ["hellocat", "apple, bat,cat,goodbye,hello,yellow,why"]. Your goal is to determine if the first element in the input can be split into two words, where both words in the dictionary that is provided in the second input. In this example, the firs element can be split into two words: hello and cat because both of those words are in the dictionary. Your program should return the two words that exist in the dictionary seperated by a comma. So for the example above, your program should return hello, cat. There will only be one correct way to split the first element of characters into two words. If there is no way to split string into two words that exist in the dictionary, return the string not possible. The first element itself will never exist in the dictionary as a real word.

My Solution

let strArr = ["baseball", "a,all,b,ball,bas,base,cat,code,d,e,quit,z"]
// let strArr = ["hellocat", "apple,bat,cat,goodbye,hello,yellow,why"]
function WordSplit(){
  // First Element, with single string   
  let wordToCompare = strArr[0]
  // Second Element, with single string   
  let stringDictionary = strArr[1]

  // Array of split strings   
  let singleStrings = stringDictionary.split(',')
  // Hold Answers   
  let answerWords = ""

  singleStrings.map((firstWord) => {

    let splitMainWordArray = wordToCompare.split(firstWord)

    if(splitMainWordArray.length > 0){

      splitMainWordArray.map((word)=>{

        let joinedWord = firstWord + word
        let reversedWord = [joinedWord].reverse().toString()

        if(joinedWord === wordToCompare || reversedWord === wordToCompare){
          // console.log(firstWord, word, 'winner')
          answerWords = "" + firstWord + ", " + word + ""
        } else {
          return 'Not Possible'
        }

      })
    }

  })

  return answerWords
}

The Process

1) First I start by grabbing the 2 elements which the problem refers to. The variable wordToCompare refers to the word that I'll be comparing. And the variable stringDictionary represents the dictionary of words string that I was provided.

2) In order to iterate over my dictionary string, I have to break it down with stringDictionary.split(',') and assign that to a variable as well to late manipulate, named singleStrings. It would look something like, ['a', 'all', 'b', ... ]'

3) I also add a variable called, singleStrings, which will be an empty string for now. Later on we can set our answer to equal this variable to return our answer out of the loops.

4) I then run a map() function on the singleStrings variable. This allows me to try and see if I can split() my wordToCompare in order to see if I can split it into two words. The problem is that I then get an array of string elements. I now have to iterate over that array to check each string and see if it can be found in the original string in any way, like baseball for example.

5) Some of the loops result in single element arrays, but I only want to look at the ones with more than one, as we're trying to split my word into two elements. For this reason I add the if(splitMainWordArray.length > 0) line.

6) I add a second map function, splitMainWordArray.map, to loop over the first arrays I got when I wrote let splitMainWordArray = wordToCompare.split(firstWord). I'm comparing the dictionary words saved in the singleStrings array and with my new arrays I'm creating each time I split a word.

7) There was a case where I was getting base from baseball, but I needed to place it inside an array to then run a .join() and .toString() in order for ballbase to equal baseball. Which is why I then write if(joinedWord === wordToCompare || reversedWord === wordToCompare).

8) If these 2 conjoined words are equal to our first string, baseball, or if reversed they're equal, we then have our answer that we concatenate and return outside of all the loops by assigning it to the emprty answerWords variable we created at the start.

Conclusion

I built this out in a CodePen if you want to play around with it. The final answer I get from our example string was base, ball. I kept trying to use regex to solve the problem but lost time researching different ways I could use match() or replace(), but at the end of they day this is how I was more quickly able to solve the problem. If anyone can complete a simpler solution with a regular expression, I'd really love to take a look!

See the Pen WordSplit by Kurt (@kurtbauer) on CodePen.

Top comments (8)

irsh5 • Aug 12 '20

If you want the solution for PHP language, then you can use below code:

function ArrayChallenge($strArr) {

  $dictWords = explode( ',', $strArr[1] );
  $strLength = strlen($strArr[0]);

  $output = 'not possible';

  for( $i = 1; $i < $strLength; $i++ ){

    $firstStr = substr($strArr[0], 0, $i);
    $lastStr = substr($strArr[0], $i, $strLength);

    if ( in_array( $firstStr, $dictWords ) && in_array( $lastStr, $dictWords ) ) {
      $output = $firstStr . ',' . $lastStr;
      break;
    }

  }

  return $output;

}

Subhash Madineni • Dec 30 '22

leetcode.com/problems/word-break
its even simpler than the above
try this:

def ArrayChallenge(strArr):
    string = strArr[0]
    dictionary = strArr[1].split(',')
    dictionary_set = set(dictionary)
    for i in range(0, len(string)):
      if string[:i] in dictionary and string[i:] in dictionary:
        return string[:i] + ","+ string[i:]

print(ArrayChallenge(["baseball", "a,all,b,ball,bas,base,cat,code,d,e,quit,z"]))
print(ArrayChallenge(["abcgefd", "a,ab,abc,abcg,b,c,dog,e,efd,zzzz"]))

K. Ashutosh Baitharu • Jun 9 '23 • Edited

The below solution seems like a better way to solve this question, this is not my solution but since I couldn't do it in my today's interview I tried finding the logic after it: youtube.com/watch?v=cHEl3u7Jk0k

let strArr = ["baseball", "a,all,b,ball,base,bas,cat,code,d,e,quit,z"]


function wordsplit(strArr){

    let firstString = strArr[0];
    let secondString = strArr[1];

    let secondArray = secondString.split(",");

    for(let i=0; i<secondArray.length; i++){

        let w1 = firstString.substr(0, i);
        let w2 = firstString.substr(i, firstString.length)

        if(secondArray.includes(w1) && secondArray.includes(w2)){
            return `${w1}${w2} - splitable`
        }
    }    
    return 'not splitable' 
    //We must keep this return outside the loop and shouldn't use return with in else operator here, 
    //cause if we do, else will be invoked as soon as the first if operator gets declined, and then else will invoke 
    //return causing the loop and function to stop.

wordsplit(strArr)

Muhammad Uzair • Jun 10 '23

It basically uses .split on second string of array and separate each word by ",". Afterwards it iterate over each separated word and check whether the second string of array includes the loop value "i" of the first string and from loop value "i" to the end of second string. if yes, than it returns replacable string else not

Rajat Sharma • May 28 '22

let strArr = ["codeaall", "a,all,b,ball,bas,base,cat,code,d,e,quit,z"]
// let strArr = ["hellocat", "apple,bat,cat,goodbye,hello,yellow,why"]
function WordSplit(){
// First Element, with single string

let wordToCompare = strArr[0];

// Array of split strings

let singleStrings = strArr[1].split(',');
let dict = {};
singleStrings.map(firstWord => dict[firstWord] = 1)

singleStrings.map((firstWord) => {
// firstWord: a,all,b,ball,bas,base,cat,code,d,e,quit,z
let splitMainWordArray = wordToCompare.split(firstWord)
console.log(firstWord, splitMainWordArray, 'splitMainWordArray')

if(splitMainWordArray.length == 2 && wordToCompare.indexOf(firstWord) > -1){
  // console.log(firstWord, word, 'test')

  // console.log(firstWord, word, joinedWord,  reversedWord);
  if(splitMainWordArray[0] == "" && dict[splitMainWordArray[1]]){
    console.log('winner')
    return "" + firstWord + ", " + splitMainWordArray[1]
  }
}

})

return "Not Possible"
}

console.log(WordSplit(strArr));