*LeetCode-Different Ways to Add Parentheses

1461 단어
괄호를 고려하지 않고 괄호를 고려하지 않는 문제는stack이라고 생각하면 틀렸어요. 분리로 귀속해야 돼요.
연산자를 만날 때마다string 양쪽을 분리하여 각각list 두 개를 계산하고 이 두 개list 안의 결과는 이 기호 배열에 따라 조합하여 계산한다
마지막 코너 케이스는 괄호가 존재하지 않습니다 즉 목록이 비어 있습니다 직접string을 추가합니다
public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> list = new ArrayList<Integer> ();
        if ( input == null || input.length() == 0 )
            return list;
        for ( int i = 0; i < input.length(); i ++ ){
            if ( input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*' ){
                List<Integer> l1 = diffWaysToCompute( input.substring( 0, i ) );
                List<Integer> l2 = diffWaysToCompute( input.substring( i + 1 ) );
                for ( int num1 : l1 ){
                    for ( int num2 : l2 ){
                        int res = 0;
                        if ( input.charAt(i) == '+' )
                            res = num1 + num2;
                        else if ( input.charAt(i) == '-')
                            res = num1 - num2;
                        else 
                            res = num1 * num2;
                        list.add ( res );
                    }
                }
            }
        }
        if ( list.size () == 0 )
            list.add ( Integer.parseInt(input) );
        return list;
    }
}

좋은 웹페이지 즐겨찾기