यहां problem राज्यों को स्ट्रिंग को कम से कम संचालन के साथ एक पैंडिंड्रोम में परिवर्तित करने के लिए कहा गया है। मैं जानता हूँ कि यह Levenshtein distance के समान है लेकिन मैं अभी तकन्यूनतम स्ट्रिंग के साथ स्ट्रिंग को पैलिंड्रोम में कैसे परिवर्तित करें?
उदाहरण के लिए इसे हल नहीं कर सकते, इनपुट mohammadsajjadhossain के लिए, उत्पादन 8 है।
स्ट्रिंग और इसके विपरीत पर लेवेनशेटिन दूरी का प्रदर्शन करें। समाधान डीपी सरणी के विकर्ण में नीचे-बाएं से ऊपर-दाएं, साथ ही साथ प्रत्येक प्रविष्टि के ऊपर और केवल विकर्ण के नीचे के संचालन में न्यूनतम संचालन होगा।
यह काम करता है क्योंकि विकर्ण के साथ प्रविष्टियां स्ट्रिंग के पहले I और अंतिम Ni वर्णों को बनाने के लिए आवश्यक न्यूनतम संपादन और केवल ऊपर की प्रविष्टियों को बनाने के लिए आवश्यक न्यूनतम संपादनों का प्रतिनिधित्व करती हैं और केवल अजीब लंबाई के साथ समाप्त होने वाली तारों के लिए न्यूनतम का प्रतिनिधित्व करती हैं मध्य (बाएं ओवर) चरित्र किसी भी चीज़ के खिलाफ मेल नहीं खाता है।
आपको प्रत्येक संभावित पालिंड्रोम पिवट बिंदु के लिए एक सीमित संख्या में लेवेनशेटिन दूरी की गणना करने की आवश्यकता है। एक पिवट पॉइंट एक पत्र हो सकता है या यह दो अक्षरों के बीच हो सकता है, इसलिए लंबाई एन की एक स्ट्रिंग में 2 एन -1 पिवट पॉइंट होते हैं। प्रत्येक धुरी लिए, आप इसे बाद धुरी से पहले पात्रों में से Levenshtein दूरी और पात्रों में से रिवर्स गणना:
(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")
m ohammadsajjadhossain: Levensthein("m", "niassohdajjasdammaho")
m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")
mo hammadsajjadhossain: Levensthein("mo", "niassohdajjasdammah")
mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")
moh ammadsajjadhossain: Levensthein("moh", "niassohdajjasdamma")
आदि
अब इन दूरीों में से कम से कम लें। यदि गति महत्वपूर्ण है, तो आप इनमें से कई कॉल को अनुकूलित कर सकते हैं।
एक अच्छा कोड गोल्फ भी ... –