Hash Table
String
Backtracking
Description
Given a pattern
and a string s
, return true
if s
matches the pattern
.
A string s
matches a pattern
if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern
is replaced by the string it maps to, then the resulting string is s
. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.
Example 1:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
Example 2:
Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"
Example 3:
Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false
Constraints:
1 <= pattern.length, s.length <= 20
pattern
and s
consist of only lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go
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 class Solution :
def wordPatternMatch ( self , pattern : str , s : str ) -> bool :
def dfs ( i , j ):
if i == m and j == n :
return True
if i == m or j == n or n - j < m - i :
return False
for k in range ( j , n ):
t = s [ j : k + 1 ]
if d . get ( pattern [ i ]) == t :
if dfs ( i + 1 , k + 1 ):
return True
if pattern [ i ] not in d and t not in vis :
d [ pattern [ i ]] = t
vis . add ( t )
if dfs ( i + 1 , k + 1 ):
return True
d . pop ( pattern [ i ])
vis . remove ( t )
return False
m , n = len ( pattern ), len ( s )
d = {}
vis = set ()
return dfs ( 0 , 0 )
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 class Solution {
private Set < String > vis ;
private Map < Character , String > d ;
private String p ;
private String s ;
private int m ;
private int n ;
public boolean wordPatternMatch ( String pattern , String s ) {
vis = new HashSet <> ();
d = new HashMap <> ();
this . p = pattern ;
this . s = s ;
m = p . length ();
n = s . length ();
return dfs ( 0 , 0 );
}
private boolean dfs ( int i , int j ) {
if ( i == m && j == n ) {
return true ;
}
if ( i == m || j == n || m - i > n - j ) {
return false ;
}
char c = p . charAt ( i );
for ( int k = j + 1 ; k <= n ; ++ k ) {
String t = s . substring ( j , k );
if ( d . getOrDefault ( c , "" ). equals ( t )) {
if ( dfs ( i + 1 , k )) {
return true ;
}
}
if ( ! d . containsKey ( c ) && ! vis . contains ( t )) {
d . put ( c , t );
vis . add ( t );
if ( dfs ( i + 1 , k )) {
return true ;
}
vis . remove ( t );
d . remove ( c );
}
}
return false ;
}
}
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 class Solution {
public :
bool wordPatternMatch ( string pattern , string s ) {
unordered_set < string > vis ;
unordered_map < char , string > d ;
return dfs ( 0 , 0 , pattern , s , vis , d );
}
bool dfs ( int i , int j , string & p , string & s , unordered_set < string >& vis , unordered_map < char , string >& d ) {
int m = p . size (), n = s . size ();
if ( i == m && j == n ) return true ;
if ( i == m || j == n || m - i > n - j ) return false ;
char c = p [ i ];
for ( int k = j + 1 ; k <= n ; ++ k ) {
string t = s . substr ( j , k - j );
if ( d . count ( c ) && d [ c ] == t ) {
if ( dfs ( i + 1 , k , p , s , vis , d )) return true ;
}
if ( ! d . count ( c ) && ! vis . count ( t )) {
d [ c ] = t ;
vis . insert ( t );
if ( dfs ( i + 1 , k , p , s , vis , d )) return true ;
vis . erase ( t );
d . erase ( c );
}
}
return false ;
}
};
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 func wordPatternMatch ( pattern string , s string ) bool {
m , n := len ( pattern ), len ( s )
vis := map [ string ] bool {}
d := map [ byte ] string {}
var dfs func ( i , j int ) bool
dfs = func ( i , j int ) bool {
if i == m && j == n {
return true
}
if i == m || j == n || m - i > n - j {
return false
}
c := pattern [ i ]
for k := j + 1 ; k <= n ; k ++ {
t := s [ j : k ]
if v , ok := d [ c ]; ok && v == t {
if dfs ( i + 1 , k ) {
return true
}
}
if _ , ok := d [ c ]; ! ok && ! vis [ t ] {
d [ c ] = t
vis [ t ] = true
if dfs ( i + 1 , k ) {
return true
}
delete ( d , c )
vis [ t ] = false
}
}
return false
}
return dfs ( 0 , 0 )
}
GitHub