CareerCup

Can be solved by dynamic programming. Let
W(k) : no of words in the string from 0 to k. If there are incomplete words then the number is infinity
word(i,k) : returns 1 if a word formed from characters in the string from i to k exists in dict else return infinity

Recursion equation
W(k+1) = min [W(i) + word(i,k+1)] for i from 1 to k

public static void stringIntoSentence(String seq, Set<String> dict) {
        StringBuffer sb = new StringBuffer();
        if (seq != null && seq.length() > 0 && dict != null && !dict.isEmpty()) {
            while (seq.length() > 0) {
                String helper = "";
                String foundIt = "";
                char[] _seq = seq.toCharArray();
                for (int i = 0; i < _seq.length; i++) {
                    helper += String.valueOf(_seq[i]);
                    if (dict.contains(helper))
                        foundIt = helper;
                }
                if (foundIt.length() > 0) {
                    seq = seq.substring(foundIt.length());
                    sb.append(foundIt);
                    if (seq.length() > 0)
                        sb.append(" ");
                } else return;
            }
        }
        System.out.println("--> " + sb.toString());
    }

def segment(str: String, dict: List[String], output: List[String]) {
if (str == "") println(output.mkString(" "))
else {
dict.foreach { word =>
if (str.startsWith(word)) {
segment(str.substring(word.length), dict, output :+ word)
}
}
}
}

This can be solved using Trie.

Assuming we have a Trie data structure with all the dictionary words in it


Basic idea is for each character keep on tracking whether the prefix it covered is a valid word or not. If it is then we have 2 subproblems

a. substring upto i is valid but need to check validity of i+1 to length subsequence.

b. ignore validity of substring 0 to i instead keep on checking validity of the subsequence from 0 to i+1

if any of the two subproblems give a result true. Overall result will be true.

public static boolean isValidSequence(Trie trie, String sequence){
		boolean rslt = false;
		int length = sequence.length();
		TrieNode node = trie.getRoot();
		int i = 0;
		for( i = 0; i < length; i++){
			char ch = sequence.charAt(i);
			int charIdx = ch - 'a';
			TrieNode[] children = node.getChildren();
			TrieNode charNode = children[charIdx];
			if(charNode == null){
				rslt = false;
				break;
				
			}
			if(charNode.isEndsWord()){
				String subSeq = sequence.substring(i+1);
				boolean rsltOfNextSeq = isValidSequence(trie, subSeq);
				if(rsltOfNextSeq){
					rslt = true;
					break;
				}
			}
			node = charNode;
		}
		if((i == length) && (node.isEndsWord()))
			rslt = true;
			
		
		return rslt;
		
	}

Not very efficient but it does the job when under the pressure and you forgot how to implement a trie

// O(n^2) running time
  def wordSeparator2(dict:Set[String], s:String):List[String] = {
     val chars = s.toCharArray

    var words = List[String]()


    var i = 0
    var j = i
    while(i < chars.size) {

      val c = chars(i)
      
      var word = ""
      var unusedChars = ""

      // be greedy and try to get the longest word
        for(j <- i to chars.length - 1) {
          if(dict.contains(word + unusedChars + chars(j))) {
            word = word + unusedChars + chars(j)
            unusedChars = ""
            i = j
          } else {
            unusedChars = unusedChars + chars(j)
          }
        }

        if(word != "")
          words = word :: words
        i = i +1
    }

    words

  }

class Solution:
    def wordBreak(self, s, wordDict):
	        #word[i] means minimum number of words in the string s[:i+1]
        w = [float('inf')] * (len(s) + 1)
        w[0]  = 0 

        for i in range(len(s)):
            for j in range(i, len(s)):
                if s[i:j+1] in wordDict:
                    w[j+1] = min(w[j+1], w[i] + 1)



        return w[-1]

Naive backtrack solution

public static void main(String[] args) {
        Set<String> dict = new HashSet<>();
        dict.add("a"); dict.add("aaa"); dict.add("name"); dict.add("is");
        String input = "aaaisaname";
        List<String> res = formattedWordWithMinimumNumber(dict, input);
        for(String s : res) {
            System.out.println(s);
        }
    }

    public static List<String> formattedWordWithMinimumNumber(Set<String> dict, String input) {
        List<String> list = new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        formattWordWithMinimumNumber(dict, input, list, res);
        List<String> minWordList = new ArrayList<>();
        StringBuilder strBuilder = new StringBuilder();
        int minNumOfWords = Integer.MAX_VALUE;
        for(int i = 0; i < res.size(); i++) {
            int listSize = res.get(i).size();
//            System.out.println(listSize);
//            if(listSize > 0)
                minNumOfWords = Math.min(listSize, minNumOfWords);
        }
        for(int i = 0; i < res.size(); i++) {
            if(res.get(i).size() == minNumOfWords) {
                minWordList.add(formatListToStr(res.get(i)));
            }
        }
        return minWordList;
    }

    public static String formatListToStr(List<String> list) {
        StringBuilder strBuilder = new StringBuilder();
        for(String s : list) {
            strBuilder.append(s+" ");
        }
        strBuilder.setLength(strBuilder.length()-1); // remove last space
        return strBuilder.toString();
    }

    public static void formattWordWithMinimumNumber(Set<String> dict, String input, List<String> list, List<List<String>> res) {
        if(input.length() == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 1; i <= input.length(); i++) {
            String current = input.substring(0,i);
            if(dict.contains(current)) {
                list.add(current);
                formattWordWithMinimumNumber(dict, input.substring(i), list, res);
                list.remove(list.size()-1);
            }
        }
    }

Brute force approach in javascript.

function longest(input, dict) {
    let res = [];

    while (input.length > 0) {
        let longest = "";

        for (var i = 1; i <= input.length; i++) {
            let test = input.substring(0, i);

            if (dict.has(test)) {
                longest = test;
            }
        }

        if (longest.length == 0) {
            throw new Error();
        }

        input = input.substring(longest.length);

        res.push(longest);
    }

    return res;
}

Word break problem but more like coin change during solution.

import UIKit

final class PTTSolution {
static let words: Set = ["a", "aa", "is", "name"]
// static let words: Set = ["a"]
class func Verify(_ input:String?) -> String? {
guard let input = input, input.count > 0 else {
return nil;
}
var lengths: Set<Int> = []
words.forEach { word in
lengths.insert(word.count)
}
var result: Array<(i: Int, w: String)> = Array(repeating: (0, ""), count: input.count + 1)
result[0] = (i: 1, w: "")
for i in 1...input.count {
lengths.forEach { length in
let startIndex = i - length
if startIndex < 0 {
return
}
let steps = result[startIndex]
if steps.i == 0 {
return
}
let start = input.index(input.startIndex, offsetBy: startIndex)
let end = input.index(input.startIndex, offsetBy: i)
let substring = String(input[start..<end])
if !words.contains(substring) {
return
}
let fullWord = steps.w.count == 0 ? substring : steps.w + " " + substring;
if (result[i].i == 0) || (result[i].i > steps.i + 1) {
result[i] = (i: steps.i + 1, w: fullWord)
}
}
}
return result.last!.w;
}
}

let input = "aaaisaname";
print(PTTSolution.Verify(input) ?? "no result");

// O(w + n*l) - where w - is number of words, n - is a number of characters in the input, l - is different lengths of word in the dictionary

Kotlin

fun test(){
        val dic : ArrayList<String> = arrayListOf("a", "aaa", "is", "name")
        val input = "aaaisaname"
        var output = StringBuilder()
        dic.map {
            if(input.contains(it)){
                if (!output.isEmpty()) output.append(" ")
                output.append(it)
            }
        }

        Log.d("TAG", output.toString())

    }

asd

I think my solution is not the most optimal but it should solve the problem.
For any permutation of words in the dictionary check if the longest common substring between concatenated dictionary's words and input string is equal to the input string.
Keep generating permutation till the match is found.