ᲘᲡᲬᲐᲕᲚᲔ

რთული

სტრინგი

მასივი

რეკურსია

backtracking

IP მისამართების აღდგენა

მოცემულია ტექსტი ip, რომელიც შეიცავს მხოლოდ ციფრებს.

თქვენი დავალებაა იპოვოთ ყველა შესაძლო ვალიდური IP მისამართი, რომელიც შეიძლება მიიღოთ წერტილების ჩასმით სტრინგში.

გადაცემული პარამეტრებიდან გამომდინარე ამოცანას აუცილებლად ექნება ერთი სწორი პასუხი.

ვალიდური IP მისამართი თუ აკმაყოფილებს შემდეგ პირობებს:

შედგება ზუსტად ოთხი მთელი რიცხვით, რომლებიც ერთმანეთისგან ერთადერთი წერტილით არიან გამოყოფილი.
თითოეული მთელი რიცხვი 0–დან 255-მდე უნდა იყოს.
არ შეიძლება იწყებოდეს ნულით (მაგალითად "01", "001" არ არის ვალიდური, გამონაკლისია "0").

მაგალითად ვალიდური მისამართებია: "192.168.0.1", "192.168.1.1".
მაგალითად არავალიდური მისამართებია: "0.011.255.245", "192.168.1.312", "192.168@1.1".

მოცემული ip ცვლადის მნიშვნელობების წაშლის ან გადაადგილების უფლება არ გაქვთ.

პირველი მაგალითი

პარამეტრები: ip = "25525511135"
შედეგი: ["255.255.11.135", "255.255.111.35"]
განმარტება: გადაცემული პარამეტრიდან შესაძლებელია მხოლოდ ამ ორი ვალიდური IP მისამართის მიღება.

მეორე მაგალითი

პარამეტრები: ip = "0000"
შედეგი: ["0.0.0.0"]
განმარტება: გადაცემული პარამეტრიდან შესაძლებელია მხოლოდ ერთი ვალიდური IP მისამართის მიღება.

მესამე მაგალითი

პარამეტრები: ip = "101023"
შედეგი: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
განმარტება: გადაცემული პარამეტრიდან შესაძლებელია მხოლოდ ხუთი ვალიდური IP მისამართის მიღება.

შეზღუდევები:

1 <= ip.length <= 20
ip შეიცავს მხოლოდ ციფრებს.

ამოცანის ამოხსნა შესაძლებელია ბევრი გზით, ცადეთ ისეთი ალგორითმის მოფიქრება, რომელიც O(1)-თან ახლოს არის.