415.字符串相加（带符号）

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

原题很简单，但如果是带符号的呢？

1. 符号处理逻辑：
   • 先分离符号和数值部分
   • 同号时直接相加保留符号
   • 异号时转换为绝对值相减
2. 数值预处理：
   • 去除前导零（removeLeadingZeros方法）
   • 处理带正号的情况（如"+123"）
3. 核心算法：
   • 加法：使用进位机制，从右到左逐位相加
   • 减法：使用借位机制，保证大数减小数
   • 比较：先比较长度，长度相同再逐位比较
4. 边界条件处理：
   • 结果为0时统一返回"0"
   • 处理全零输入（如"0000"）
   • 处理符号冲突（如正负零）

• 时间复杂度：O(max(M,N))
  • 加减法操作需要遍历最长数字的所有位数
  • 比较操作需要O(N)时间
• 空间复杂度：O(max(M,N))
  • 存储结果需要与输入规模相当的额外空间

public class SignedBigNumberAddition {

    public String addStringsWithSign(String num1, String num2) {
        // 处理空输入
        if (num1 == null || num1.isEmpty()) return num2;
        if (num2 == null || num2.isEmpty()) return num1;

        // 解析符号和数值部分
        boolean isNegative1 = num1.charAt(0) == '-';
        boolean isNegative2 = num2.charAt(0) == '-';
        String n1 = isNegative1 ? num1.substring(1) : num1;
        String n2 = isNegative2 ? num2.substring(1) : num2;
        
        // 处理正号情况（如"+123"）
        if (!isNegative1 && !n1.isEmpty() && num1.charAt(0) == '+') {
            n1 = num1.substring(1);
        }
        if (!isNegative2 && !n2.isEmpty() && num2.charAt(0) == '+') {
            n2 = num2.substring(1);
        }
        
        // 去除前导零
        n1 = removeLeadingZeros(n1);
        n2 = removeLeadingZeros(n2);

        // 处理符号逻辑
        if (isNegative1 == isNegative2) { // 同号相加
            String sum = add(n1, n2);
            return (isNegative1 && !sum.equals("0")) ? "-" + sum : sum;
        } else { // 异号相减
            int compare = compare(n1, n2);
            if (compare == 0) return "0";
            
            if (compare > 0) {
                String difference = subtract(n1, n2);
                return isNegative1 ? "-" + difference : difference;
            } else {
                String difference = subtract(n2, n1);
                return isNegative2 ? "-" + difference : difference;
            }
        }
    }

    // 辅助方法：字符串加法（处理非负数）
    private String add(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length()-1, j = num2.length()-1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int n1 = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            sb.append(sum % 10);
        }
        return formatResult(sb.reverse());
    }

    // 辅助方法：字符串减法（保证num1 >= num2）
    private String subtract(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length()-1, j = num2.length()-1;
        int borrow = 0;
        
        while (i >= 0 || j >= 0) {
            int n1 = (i >= 0 ? num1.charAt(i--) - '0' : 0) - borrow;
            int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
            
            borrow = 0;
            if (n1 < n2) {
                n1 += 10;
                borrow = 1;
            }
            sb.append(n1 - n2);
        }
        return formatResult(sb.reverse());
    }

    // 辅助方法：比较两个非负数字字符串大小
    private int compare(String num1, String num2) {
        if (num1.length() != num2.length()) {
            return num1.length() > num2.length() ? 1 : -1;
        }
        for (int i = 0; i < num1.length(); i++) {
            char c1 = num1.charAt(i);
            char c2 = num2.charAt(i);
            if (c1 != c2) {
                return c1 > c2 ? 1 : -1;
            }
        }
        return 0;
    }

    // 辅助方法：去除前导零
    private String removeLeadingZeros(String num) {
        int start = 0;
        while (start < num.length() && num.charAt(start) == '0') {
            start++;
        }
        return start == num.length() ? "0" : num.substring(start);
    }

    // 辅助方法：格式化结果（去除前导零）
    private String formatResult(CharSequence num) {
        int start = 0;
        while (start < num.length() && num.charAt(start) == '0') {
            start++;
        }
        return start == num.length() ? "0" : num.subSequence(start, num.length()).toString();
    }
}