Eric Yuan's Blog

Perstando et Praestando

  • About Me

[LeetCode] Word Break

January 15, 2014 / Leave a Comment

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Most of problems that return a bool value or int value (amount) in LeetCode can be solved using Dynamic Programming.

We can define something named “record(a, b)”, which means the sub-string start from a and has b length can be constructed with words in dictionary. Here’s an example.

find “karanokyoukai” in this dictionary: (空の境界)

“ka“, “o“, “anok“, “ok“, “kai“, “no“, “kala“, “ran“, “you“, “kyou“.

Using Dynamic Programming, we can get this record:

1

 

For example, we can see in first ‘k’ row, the ‘2’ column is TRUE, because we can find “ka” word in dictionary; for same reason, in first ‘k’ row, the ‘7’ column is TRUE, because we can find “ka”, “ran”, “ok” in dictionary.

Then all we need to do is to check the value of record(0, len), it is 1, that means the sub-string which start from 0, and have len length, can be broken to elements in dictionary.

    bool wordBreak(string s, unordered_set<string> &dict) {
        int length = s.size();
        bool **record = new bool*[length];
        for(int i=0; i < length; i++){
            record[i] = new bool[length];
        }
        for(int i = 0; i < length; i ++){
            for(int j = 0; j < length; j++){
                record[i][j] = false;
            }
        }
        for(int i = 0; i < length; ++ i){
            for(int len = 0; len < length - i; ++ len){
                string subword = s.substr(i,len + 1);
                if(dict.find(subword) != dict.end()){
                    record[i][len] = true;
                    if(i > 0 && record[0][i - 1]){
                        record[0][i + len] = true;  
                    } 
                }
            }
        }
        return record[0][length - 1];
    }

🙂

 

Posted in: Algorithm, Dynamic Programming, LeetCode Tagged: Algorithm, Dynamic Programming, LeetCode

Pages

  • About Me

Categories

  • Algorithm
  • Deep Learning
  • Dynamic Programming
  • Graphics
  • LeetCode
  • Machine Learning
  • Machine Reading Comprehension
  • Maths
  • NLP
  • OpenCV
  • Something else
  • Twaddle
  • Uncategorized
  • Vision

Archives

  • July 2016
  • August 2015
  • June 2015
  • April 2015
  • March 2015
  • October 2014
  • September 2014
  • July 2014
  • June 2014
  • May 2014
  • April 2014
  • March 2014
  • February 2014
  • January 2014
  • November 2013
  • October 2013
  • September 2013

Copyright © 2018 Eric Yuan's Blog.

Me WordPress Theme by themehall.com