ได้รับสตริงตัวเลข s และ t ต้องลบตัวเลขออกจากทั้งสองสตริง จน ทั้งสองสตริงเหมือนกัน และ ผลรวมตัวเลขที่ลบออกน้อยที่สุด คืนค่าผลรวมนั้น
ตัวอย่าง
Input: s = "41272", t = "172"
Output: 6
ลบ '4' และ '2' จาก s → "172" ผลรวม = 4+2=6
แนวทางแก้ปัญหา
เทียบเท่ากับการหา Maximum Sum Common Subsequence:
- LCS แบบปกติหา "ความยาว" สูงสุด → ที่นี่หา "ผลรวมตัวเลข" สูงสุด
- DP table:
dp[i][j]= max sum ของ common subsequence ของs[:i]และt[:j] - ถ้า
s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 2*digit(×2 เพราะเก็บได้ในทั้งสองสตริง) - มิฉะนั้น:
max(dp[i-1][j], dp[i][j-1]) - คำตอบ =
sum(s) + sum(t) - dp[m][n]
การใช้งาน (Python)
class Solution:
def lcs(self, a, b, m, n):
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48)
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def solve(self, a, b):
m, n = len(a), len(b)
total = sum(ord(c) - 48 for c in a) + sum(ord(c) - 48 for c in b)
return total - self.lcs(a, b, m, n)
# ทดสอบ
ob = Solution()
print(ob.solve("41272", "172")) # Output: 6
ความซับซ้อน
- Time Complexity: O(m × n)
- Space Complexity: O(m × n)
