leetcode 67. 二进制求和 解题思路

闲太久了，前两天又开始重新刷题啦，就从leetcode上的每日一题开始吧。

67. 二进制求和：

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路

首先取a,b中较长一方的长度，新建一个数据，用来保存求和（不用担心溢出，最后会说）。然后设置一个left变量用来保存进位，开始从双方末尾开始相加，计算a[i]+b[i]+left，sum[i]为计算出来的和对2取余，left重新赋值为计算出来的和除以2。一直相加到第一位为止，此时如果进位为0，直接返回sum，如果进位为1，返回“1”+sum。
注意在计算过程中不要数组越界，取数前先判断一下。

总的这道题比较简单，之前想用位运算来做但是发现还是要保存进位，但是发现还是要保存进位，和现在的方法没有区别。也可能是我想歪了，欢迎各位大佬指正。

下附java代码仅供参考:

public class SumOfTwobinary67 {
    public static void main(String[] args) {
        System.out.println(addBinary("01100", "111000"));
    }

    public static String addBinary(String a, String b) {
        char[] as = a.toCharArray();
        char[] bs = b.toCharArray();
        int maxLeng = as.length > bs.length ? a.length() : b.length();
        char[] sum = new char[maxLeng];
        int left = 0;
        for (int i = 0; i < maxLeng; i++) {
            int cur = 0;
            if (a.length() - i > 0) {
                cur += as[a.length() - i - 1] - '0';
            }
            if (b.length() - i > 0) {
                cur += bs[b.length() - i - 1] - '0';
            }
            cur += left;
            left = cur / 2;
            sum[maxLeng - i - 1] = (char) (cur % 2 + '0');
        }
        if (left == 0) {
            return String.copyValueOf(sum);
        } else {
            return "1" + String.copyValueOf(sum);
        }
    }
}