题目描述
哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"
已经变成了"iresetthecomputeritstilldidntboot"
。在处理标点符号和大小写之前,你得先把它断成词语。当然了,你有一本厚厚的词典dictionary
,不过,有些词没在词典里。假设文章用sentence
表示,设计一个算法,把文章断开,要求未识别的字符最少,返回未识别的字符数。
注意: 本题相对原题稍作改动,只需返回未识别的字符数
示例:
输入:
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出: 7
解释: 断句后为"jess looked just like tim her brother",共7个未识别字符。
提示:
0 <= len(sentence) <= 1000
dictionary
中总字符数不超过 150000。
你可以认为dictionary
和sentence
中只包含小写字母。
解法
方法一:动态规划
Python3 Java C++ Go Swift
class Solution :
def respace ( self , dictionary : List [ str ], sentence : str ) -> int :
s = set ( dictionary )
n = len ( sentence )
dp = [ 0 ] * ( n + 1 )
for i in range ( 1 , n + 1 ):
dp [ i ] = dp [ i - 1 ] + 1
for j in range ( i ):
if sentence [ j : i ] in s :
dp [ i ] = min ( dp [ i ], dp [ j ])
return dp [ - 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public int respace ( String [] dictionary , String sentence ) {
Set < String > dict = new HashSet <> ( Arrays . asList ( dictionary ));
int n = sentence . length ();
int [] dp = new int [ n + 1 ] ;
for ( int i = 1 ; i <= n ; i ++ ) {
dp [ i ] = dp [ i - 1 ] + 1 ;
for ( int j = 0 ; j < i ; ++ j ) {
if ( dict . contains ( sentence . substring ( j , i ))) {
dp [ i ] = Math . min ( dp [ i ] , dp [ j ] );
}
}
}
return dp [ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
int respace ( vector < string >& dictionary , string sentence ) {
unordered_set < string > s ( dictionary . begin (), dictionary . end ());
int n = sentence . size ();
vector < int > dp ( n + 1 );
for ( int i = 1 ; i <= n ; ++ i ) {
dp [ i ] = dp [ i - 1 ] + 1 ;
for ( int j = 0 ; j < i ; ++ j ) {
if ( s . count ( sentence . substr ( j , i - j ))) {
dp [ i ] = min ( dp [ i ], dp [ j ]);
}
}
}
return dp [ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func respace ( dictionary [] string , sentence string ) int {
s := map [ string ] bool {}
for _ , v := range dictionary {
s [ v ] = true
}
n := len ( sentence )
dp := make ([] int , n + 1 )
for i := 1 ; i <= n ; i ++ {
dp [ i ] = dp [ i - 1 ] + 1
for j := 0 ; j < i ; j ++ {
if s [ sentence [ j : i ]] {
dp [ i ] = min ( dp [ i ], dp [ j ])
}
}
}
return dp [ n ]
}
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 class TrieNode {
var children : [ TrieNode ?] = Array ( repeating : nil , count : 26 )
var isEndOfWord = false
}
class Trie {
private let root = TrieNode ()
func insert ( _ word : String ) {
var node = root
for char in word {
let index = Int ( char . asciiValue ! - Character ( "a" ). asciiValue !)
if node . children [ index ] == nil {
node . children [ index ] = TrieNode ()
}
node = node . children [ index ] !
}
node . isEndOfWord = true
}
func search ( _ sentence : Array < Character >, start : Int , end : Int ) -> Bool {
var node = root
for i in start ... end {
let index = Int ( sentence [ i ]. asciiValue ! - Character ( "a" ). asciiValue !)
guard let nextNode = node . children [ index ] else {
return false
}
node = nextNode
}
return node . isEndOfWord
}
}
class Solution {
func respace ( _ dictionary : [ String ], _ sentence : String ) -> Int {
let n = sentence . count
guard n > 0 else { return 0 }
let trie = Trie ()
dictionary . forEach { trie . insert ( $0 ) }
let chars = Array ( sentence )
var dp = Array ( repeating : Int . max , count : n + 1 )
dp [ 0 ] = 0
for i in 1. .. n {
dp [ i ] = dp [ i - 1 ] + 1
for j in 0. .< i {
if trie . search ( chars , start : j , end : i - 1 ) {
dp [ i ] = min ( dp [ i ], dp [ j ])
}
}
}
return dp [ n ]
}
}
GitHub