14. Longest Common Prefix

Đề bài

Cho một mảng chuỗi strs, hãy tìm chuỗi tiền tố chung dài nhất của tất cả các chuỗi trong mảng.

Nếu không có tiền tố chung, trả về chuỗi rỗng "".

Ví dụ 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Ví dụ 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: Không có tiền tố chung giữa các chuỗi.

Ràng buộc:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] chỉ gồm chữ cái tiếng Anh thường.

Tóm tắt đề

Tìm chuỗi prefix dài nhất sao cho prefix là tiền tố của mọi phần tử trong strs.

Ý tưởng

Trong code bên dưới:

• Khởi tạo prefix = strs[0].
• Duyệt từng chuỗi còn lại, và so sánh từng ký tự với prefix.
• Nếu gặp vị trí không khớp (hoặc chuỗi hiện tại đã hết) thì cắt ngắn prefix lại: prefix = prefix[:j].
• Kết thúc vòng lặp, prefix chính là tiền tố chung dài nhất.

Code

package leetcode

func longestCommonPrefix(strs []string) string {
	prefix := strs[0]

	for i := 1; i < len(strs); i++ {
		for j := 0; j < len(prefix); j++ {
			if len(strs[i]) <= j || strs[i][j] != prefix[j] {
				prefix = prefix[0:j]
				break
			}
		}
	}

	return prefix
}

---