FilesExpand file tree

 master

/

WordBreakII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (56 loc) · 1.81 KB

 master

/

WordBreakII.java

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (56 loc) · 1.81 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

package dynamic_programming;

import java.util.*;

/**

* Created by gouthamvidyapradhan on 07/04/2017. Given a non-empty string s and a dictionary

* wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each

* word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

*

* <p>Return all such possible sentences.

*

* <p>For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

*

* <p>A solution is ["cats and dog", "cat sand dog"].

*/

public class WordBreakII {

private Map<Integer, List<String>> map;

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

List<String> wordList = new ArrayList<>();

wordList.add("cat");

wordList.add("cats");

wordList.add("and");

wordList.add("sand");

wordList.add("dog");

System.out.println(new WordBreakII().wordBreak("catsanddog", wordList));

}

public List<String> wordBreak(String s, List<String> wordDict) {

if (s == null) return new ArrayList<>();

map = new HashMap<>();

Set<String> dictionary = new HashSet<>();

dictionary.addAll(wordDict);

return dp(0, s, s.length(), dictionary);

}

private List<String> dp(int p, String s, int l, Set<String> dictionary) {

List<String> result = new ArrayList<>();

if (p >= s.length()) {

result.add("");

return result;

} else if (map.containsKey(p)) {

return map.get(p);

}

for (int i = p; i < l; i++) {

String subStr = s.substring(p, i + 1);

if (dictionary.contains(subStr)) {

List<String> subList = dp(i + 1, s, l, dictionary);

for (String se : subList) result.add((subStr + " " + se).trim());

}

}

map.put(p, result);

return result;

}

}