पायथन में गलत लिखे शब्द को ठीक करने के लिए बदले जाने वाले कुल वर्णों की संख्या ढूंढने का प्रोग्राम

मान लीजिए हमें शहरों की एक लिस्ट और सड़कों की एक लिस्ट दी गई है जो एक-दूसरे को जोड़ती हैं। 'cities' लिस्ट में उन शहरों के नाम हैं जिन्हें एक टूर बस क्रम से देखती है। 'roads' लिस्ट में सड़कें (स्रोत, गंतव्य) क्रम में सूचीबद्ध हैं जिसका अर्थ है स्रोत से गंतव्य तक एक वन-वे सड़क है। अब, एक समस्या है कि 'cities' लिस्ट में कुछ शहरों के नाम गलत लिखे हो सकते हैं। हमें ऐसे गलत लिखे शहरों के नामों को न्यूनतम वर्णों को बदलकर ठीक करना है। हम आउटपुट के रूप में बदले गए वर्णों की संख्या लौटाते हैं।

इसलिए, यदि इनपुट cities = ["HWH", "DLI", "BGL"], roads = [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]] है, तो आउटपुट 2 होगा।

cities में गलत लिखा शहर का नाम 'BGL' है। सही नाम 'BCT' होगा। तो, cities में नाम को ठीक करने के लिए हमें 2 वर्ण बदलने होंगे।

समाधान दृष्टिकोण

diff() फंक्शन परिभाषित करें दो स्ट्रिंग्स के बीच वर्ण अंतर की गणना के लिए
डायनामिक प्रोग्रामिंग का उपयोग करके न्यूनतम संपादन दूरी ट्रैक करें
वैध रोड ट्रांजिशन के माध्यम से पुनरावृति करें
सभी वैध पथों में न्यूनतम कुल परिवर्तन लौटाएं

उदाहरण कार्यान्वयन

def diff(a, b):
    return sum(x != y for x, y in zip(a, b))

def solve(cities, roads):
    size = len(cities)
    arr = dict()
    junctions = set(r[0] for r in roads)
    for j in junctions:
        arr[j] = diff(cities[0], j)
    for i in range(1, size):
        nxt = dict()
        for r1, r2 in roads:
            if r1 in arr:
                cost = arr[r1] + diff(cities[i], r2)
                if r2 not in nxt or cost < nxt[r2]:
                    nxt[r2] = cost
        arr = nxt
    return min(arr.values())

print(solve(["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]))

इनपुट

["HWH", "DLI", "BGL"], [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]