648.md

648. Replace word

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Note:
The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

my thoughts:

1. convert the dict into a first letter dict. for each word, check the first letter then see if the root is in the big dict.

my solution:

**********956ms
class Solution(object):
    def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        ld = {}
        for w in dict:
            if w[0] not in ld:
                ld[w[0]] = [len(w)]
            else:
                ld[w[0]].append(len(w))
                
        temp = sentence.split(' ')
        res = []
        for w in temp:
            if w[0] in ld:
                posi_l = sorted(list(set(ld[w[0]])))
                for l in posi_l:
                    if l<=len(w) and w[:l] in dict:
                        w = w[:l]
                        break
            res.append(w)
        return ' '.join(res)

my comments:

from other ppl's solution:

1. str.startswith() seems save a lot of time, 65 ms:
class Solution(object):
    def replaceWords(self, d, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        d.sort()
        ddd = {}
        for item in d:
            if item[0] in ddd:
                ddd[item[0]].append(item)
            else:
                ddd[item[0]] = [item]
        sens = sentence.split(' ')
        for index in xrange(len(sens)):
            for ww in ddd.get(sens[index][0],[]):
                if sens[index].startswith(ww):
                    sens[index] = ww
                    break
        return ' '.join(sens)
		
2. modifying my solution, 77ms: # should sort the dict first...
class Solution(object):
    def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        ld = {}
        for w in dict:
            if w[0] not in ld:
                ld[w[0]] = [w]
            else:
                ld[w[0]].append(w)
                
        temp = sentence.split(' ')
        res = []
        for w in temp:
            if w[0] in ld:
                for key in ld[w[0]]:
                    if w.startswith(key):
                        w = key
                        break
            res.append(w)
        return ' '.join(res)