-3

I write a program to find the longest word made of other words that is also present in array.

  sort_arr.forEach(word => {
     if (isLargest(word, word)) {
        console.log(word);
     }
   });

    function isLargest(initialWord, word) {
    let first_half = 0;
    let second_half = 0;
    let start = 0;
    let end = 0;
    for (let i = 0; i < word.length; i++) {
        end++;
        first_half = word.substring(start, end);

        for (let j = 0; j < sort_arr.length; j++) {
            if (first_half === sort_arr[j]) {
                second_half = word.substring(end, word.length);
                if(second_half === ''){
                    return word !== initialWord;
                }
                else{
                    return isLargest(initialWord, second_half);
                }
            }
        }

    }
}

But there is a problem when array words contain 

[ 'catxdogcatsrat',
  'catsdogcats',
  'dogcatsdog',
  'cats',
  'cat',
  'dog',
  'rat' ]

It gives output null

But the result should comes catsdogcats

I know the problem is occuring when in catsdogcats, prefix is cat and suffix is sdogcats. But it is not checking for prefix cats and suffix dogcats.

Can please some one suggest me some ways to do this without using ties.

Rupesh Yadav
  • 27
  • 8

2 Answers2

0

This is a bit more complicated than first anticipated. You have to see what other words are the same as the start of the current word and try with every of those words until you get the complete word made up of the other words.

const canMakeWord = (array, word) => {
  //recursive function
  const recur = (array, word) => {
    //word passed is empty, so we could make current word
    //  with the list of other words
    if (word === '') {
      return true;
    }
    //see what words in the list of other words
    //  can start to make up this word
    const candidates = array.filter(
      (otherWord) => word.indexOf(otherWord) === 0,
    );
    if (!candidates.length) {
      console.warn('giving up for word', word);
    }
    return (
      //no candidates, return false
      !!candidates.length &&
      //try each candidate recursively
      candidates.reduce(
        (result, otherWord) =>
          result || //try for every result until it's true
          //use whole list of other words but remove
          //  the other word used for this check from
          //  current word
          console.log(
            'trying with word:',
            word,
            'using candidate:',
            JSON.stringify(otherWord),
          ) ||
          recur(array, word.replace(otherWord, '')),
        false,
      )
    );
  };
  //return recursive function
  return recur(
    array
      //do not use other words that are longer than current word
      .filter((w) => w.length <= word.length)
      //do not include current word
      .filter((w) => w !== word),
    word,
  );
};

const words = ['x', 'xxs', 'xxsxxsxx'];
const result = words
  .map((word) => [word.length, word])
  .sort(([a], [b]) => b - a)
  .map(([_, word]) => word)
  .find(
    (word, index, all) =>
      canMakeWord(all, word),
  );
// .map((word, index, all) => [canMakeWord(all, word), word])
// //take out all words that could not have been made up out of
// //  other words
// .filter(([canMake]) => canMake)
// .map(
//   //map to [wordLength,word]
//   ([_, word]) => [word.length, word],
// )
// .sort(
//   ([a], [b]) => b - a, //sort to longest word
// );
console.log('RESULT:');
console.log(result);
HMR
  • 37,593
  • 24
  • 91
  • 160
  • It good for small arrays, but taking too much time for the very large array. – Rupesh Yadav Aug 30 '18 at 15:14
  • @RupeshYadav you could sort words by longest word first and quit when the first word is found that could be made up of all the other words. If there are more than one longest (like the longest is 6 and you have several words that are 6 long that can be created with other words from the array) then you would get incorrect result (only one of them). I updated the answer to do so. Also remove the console.logs as they are only there to show how the code works (try to match everything with everything as you stated in your comment: `You can use any words any time`). – HMR Aug 31 '18 at 06:49
  • @RupeshYadav You could repeat it with the longest word taken out of the array. – HMR Sep 03 '18 at 06:54
0

Not sure if this is what you want, but findLongestCombination(arr) returns the longest combination of a word being built out of other words (using each word just once) in an array. In this case: ["123, "111", "1", "3"]

It does that by trying out every possible way of building a word, using findLongestCombinationSingle(word, otherWords) recursively, which finds the longest combination of building one word out of the remaining ones.

If you have questions, or I did not understand the issue, feel free to comment.

arr = ['123', '111', '12311113', '1', '2', '3'];

console.log(findLongestCombination(arr));

function findLongestCombination(arr){
  var result = [];
  for(var i=0; i<arr.length; i++){
    var arrOthers = arr.slice(0,i).concat(arr.slice(i+1));
    var comb = findLongestCombinationSingle(arr[i], arrOthers);
    if(comb.length > result.length) result = comb;
  }
  return result;
}

function findLongestCombinationSingle(word, otherWords){
    var result = [];
    for(var i=0; i<otherWords.length; i++){
    if(word.startsWith(otherWords[i])){
        var wordsLeft = otherWords.slice(0,i).concat(otherWords.slice(i+1));
      var restWord = word.replace(otherWords[i], "");
      var subresult = [otherWords[i]].concat(findLongestCombinationSingle(restWord, wordsLeft));
      if(subresult.length > result.length) result = subresult;
    }
  }
  return result;
}

It doesn't break if a word is non combinable... Gotta fix that, give me some time

d0n.key
  • 1,318
  • 2
  • 18
  • 39