Nhờ mọi người giúp challenge Attribute Parser trên Hackerrank

#1

Mọi người có thể cho em hướng đi của challenge trên kia ko? E thực sự ko biết làm j luôn mặc dù hiểu đề bài rồi !
Cụ thể là em ko biết dùng string như thế nào để lưu từng element, attribute và value của nó luôn :frowning:
E cảm on trc nhé :smiley:

#2

Mình nghĩ ntn:

Parse thành cây. Với mỗi node có value là 1 map(attr, value)

Để parse được thì đầu tiên split theo khoảng trắng
-> [<tag_name, attr-name, =, value, attr_name2, =, value2, >]

Tạo node mới map(attr, value) = value của node này.
Xem trong stack có node cha nào không

  • nếu có:
    Pop node trong đỉnh stack ra (parentNode)
    Tạo node con cho parentNode là node vừa được tạo
    Push lại parentNode vào stack
    Push vào stack node vừa tạo.
  • nếu không có thì:
    Push node vừa tạo vào stack
    Tạo 1 entry cho map(tagname, address) với tagname và address của node vừa tạo

Đọc dòng tiếp, nếu dòng tiếp là 1 tag đóng thì pop node trên đỉnh stack ra.

Tiếp theo là đọc các query,
tag1.tag2~name
-> kiếm trong map tag1 -> lấy ra đc address root tag1
từ root BFS or DFS tìm ra node con là tag2.
rồi từ tag2 ta lấy value.getValue(name) (do value như nói ở trên là 1 map) là ra được value của attr name :3

Không biết có cách nào hay hơn ko nhỉ :?

2 Likes
#3

Ezz, còn cách nào đơn giản hơn ko a? :smiley:
Chứ em chưa học tới cây và DSLK nữa.
Mà ko biết là số lượng attributes có hạn chế ko ta? Nếu chỉ có mỗi 2 attributes là name và value đc thì tốt qu1 :smiley:

#4

Đây là 1 testcase em lụm đc trong discussion:

12 8
<tag1 value = "HelloWorld">
	<tag2 name = "Name1">
		<tag3 name = "Name3">
		</tag3>
		<tag4 name = "Name4" text = "Super">
			<tag6 buzz = "Buzz6">
			</tag6>
		</tag4>
		<tag5>
		</tag5>
	</tag2>
</tag1>
tag1.tag2~name
tag1~name
tag1~value
tag1.tag2.tag3~name
tag1.tag2.tag3~value
tag1.tag2.tag4~text
tag1.tag2.tag4.tag6~text
tag1.tag2.tag4.tag6~buzz

testcase như thế thì còn đâu đất sống :cry:

#5

THấy đề ghi attr_name1, attr_name2 :v
ko có vụ attr_name_n -> chắc là chỉ có tối đa 2 attribute thôi đó.
Mà thấy nó để dấu … nên chắc cũng có? :))

1 Like
#6

tạo 1 cái struct

struct Tag {
    std::string fullName;
    std::map<std::string, std::string> attributes;
};

rồi phang thôi, chả cần quan tâm node con node cha gì hết, vì N <= 20 nên số tag tối đa là 10, cho hết mấy cái tag này vô 1 mảng rồi tìm từ đầu tới cuối mảng, khỏi cần duyệt cây chi cho khổ.

lúc đọc thì nhớ cái fullName, ví dụ khi đọc cái test case 12 8 kia thì fullName lần lượt là
tag1
tag1.tag2
tag1.tag2.tag3
tag1.tag2 (pop)
tag1.tag2.tag4
tag1.tag2.tag4.tag6
tag1.tag2.tag4 (pop)
tag1.tag2 (pop)
tag1.tag2.tag5
tag1.tag2 (pop)
tag1 (pop)

gặp </ thì pop cái tag cuối ra khỏi fullName, còn bình thường thì push tên tag mới vô fullName. Vậy là có fullName của mỗi tag.

lúc query chỉ cần tách query ra làm fullName với attrName, rồi tìm trong mảng tags coi tag nào có fullName như query, rồi xuất tag.attrbutes[attrName] là xong. Nhớ ktra coi có tag nào có fullName như query, và phải có attrName trong attributes.

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?