Description
Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
Example 1:
Input: s = "1^0|0|1", result = 0
Output: 2
Explanation: Two possible parenthesizing ways are:
1^(0|(0|1))
1^((0|0)|1)
Example 2:
Input: s = "0&0&0&1^1|0", result = 1
Output: 10
Note:
There are no more than 19 operators in s.
Solutions
Solution 1
Python3 Java C++ Go Swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution :
def countEval ( self , s : str , result : int ) -> int :
@cache
def dfs ( s ):
res = [ 0 ] * 2
if s in '01' :
res [ int ( s )] = 1
return res
for k , op in enumerate ( s ):
if op in '&^|' :
left , right = dfs ( s [: k ]), dfs ( s [ k + 1 :])
for i , v1 in enumerate ( left ):
for j , v2 in enumerate ( right ):
if op == '&' :
v = i & j
elif op == '^' :
v = i ^ j
elif op == '|' :
v = i | j
res [ v ] += v1 * v2
return res
ans = dfs ( s )
return ans [ result ] if 0 <= result < 2 else 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 class Solution {
private Map < String , int []> memo ;
public int countEval ( String s , int result ) {
memo = new HashMap <> ();
int [] ans = dfs ( s );
return result == 0 || result == 1 ? ans [ result ] : 0 ;
}
private int [] dfs ( String s ) {
if ( memo . containsKey ( s )) {
return memo . get ( s );
}
int [] res = new int [ 2 ] ;
if ( s . length () == 1 ) {
res [ Integer . parseInt ( s ) ] = 1 ;
return res ;
}
for ( int k = 0 ; k < s . length (); ++ k ) {
char op = s . charAt ( k );
if ( op == '&' || op == '|' || op == '^' ) {
int [] left = dfs ( s . substring ( 0 , k ));
int [] right = dfs ( s . substring ( k + 1 ));
for ( int i = 0 ; i < 2 ; ++ i ) {
for ( int j = 0 ; j < 2 ; ++ j ) {
int v = 0 ;
if ( op == '&' ) {
v = i & j ;
} else if ( op == '|' ) {
v = i | j ;
} else if ( op == '^' ) {
v = i ^ j ;
}
res [ v ] += left [ i ] * right [ j ] ;
}
}
}
}
memo . put ( s , res );
return res ;
}
}
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 class Solution {
public :
unordered_map < string , vector < int >> memo ;
int countEval ( string s , int result ) {
vector < int > ans = dfs ( s );
return result == 0 || result == 1 ? ans [ result ] : 0 ;
}
vector < int > dfs ( string s ) {
if ( memo . count ( s )) return memo [ s ];
vector < int > res ( 2 );
if ( s . size () == 1 ) {
res [ s [ 0 ] - '0' ] = 1 ;
return res ;
}
for ( int k = 0 ; k < s . size (); ++ k ) {
if ( s [ k ] == '0' || s [ k ] == '1' ) continue ;
vector < int > left = dfs ( s . substr ( 0 , k ));
vector < int > right = dfs ( s . substr ( k + 1 , s . size () - k ));
for ( int i = 0 ; i < 2 ; ++ i ) {
for ( int j = 0 ; j < 2 ; ++ j ) {
int v = 0 ;
if ( s [ k ] == '&' )
v = i & j ;
else if ( s [ k ] == '|' )
v = i | j ;
else if ( s [ k ] == '^' )
v = i ^ j ;
res [ v ] += left [ i ] * right [ j ];
}
}
}
memo [ s ] = res ;
return res ;
}
};
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 func countEval ( s string , result int ) int {
memo := map [ string ][] int {}
var dfs func ( string ) [] int
dfs = func ( s string ) [] int {
if v , ok := memo [ s ]; ok {
return v
}
res := make ([] int , 2 )
if len ( s ) == 1 {
res [ s [ 0 ] - '0' ] = 1
return res
}
for k , c := range s {
if c == '0' || c == '1' {
continue
}
left , right := dfs ( s [: k ]), dfs ( s [ k + 1 :])
for i , v1 := range left {
for j , v2 := range right {
v := 0
if c == '&' {
v = i & j
} else if c == '|' {
v = i | j
} else if c == '^' {
v = i ^ j
}
res [ v ] += v1 * v2
}
}
}
memo [ s ] = res
return res
}
ans := dfs ( s )
if result == 0 || result == 1 {
return ans [ result ]
}
return 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
47
48 class Solution {
private var memo = [ String : [ Int ]]()
func countEval ( _ s : String , _ result : Int ) -> Int {
memo = [:]
let ans = dfs ( s )
return result == 0 || result == 1 ? ans [ result ] : 0
}
private func dfs ( _ s : String ) -> [ Int ] {
if let res = memo [ s ] {
return res
}
var res = [ 0 , 0 ]
if s . count == 1 {
res [ Int ( String ( s )) ! ] = 1
return res
}
for k in 0. .< s . count {
let index = s . index ( s . startIndex , offsetBy : k )
let op = String ( s [ index ])
if op == "&" || op == "|" || op == "^" {
let left = dfs ( String ( s [ s . startIndex ..< index ]))
let right = dfs ( String ( s [ s . index ( after : index )...]))
for i in 0. .. 1 {
for j in 0. .. 1 {
var v = 0
if op == "&" {
v = i & j
} else if op == "|" {
v = i | j
} else if op == "^" {
v = i ^ j
}
res [ v ] += left [ i ] * right [ j ]
}
}
}
}
memo [ s ] = res
return res
}
}
GitHub
