LintCode: Word Synthesis Problem

Word Synthesis Problem



Similar Problems:


Description
Given a target word targets and a collection of n words words, can you select some words from words and select one letter from each word to compose the target word target ?

Only lowercase letters a-z will be included in the string
target is no longer than 20, each word in words is no more than 20, and words is no more than 20.

Example

Given target="ally",words=["buy","discard","lip","yep"],return false

Explanation:
'buy' can match 'y', 'discard' can match 'a', 'lip' can match 'l', 'yep' cannot correspond to any one letter, so there is still one 'l' in 'target' that cannot be matched. 
Given target="ray",words=["buy","discard","lip","rep"],return true

Explanation:
'buy' can match 'y', 'discard' can match 'a', 'rep' can match 'r'.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution: dfs
// Blog link: https://code.dennyzhang.com/word-synthesis-problem
// Basic Ideas: dfs
// Complexity: 
/**
 * @param target: the target string
 * @param words: words array
 * @return: whether the target can be matched or not
 */
var visited = map[int]bool{}
var chMap = map[rune][]int{}

func dfs(target string) bool {
    if target == "" { return true }
    ch := rune(target[0])
    for _, index := range chMap[ch] {
        if visited[index] == false {
            visited[index] = true
            if dfs(target[1:]) == true { return true }
            visited[index] = false
        }
    }
    return false
}

func matchFunction (target string, words []string) bool {
    for i, word := range words {
        for _, ch := range word {
            chMap[ch] = append(chMap[ch], i)
        }
    }
    return dfs(target)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.