जावास्क्रिप्ट का उपयोग करके 1 या 2 वर्णों को हटाकर एक पैलिंड्रोम कैसे बनाएं आपके द्वारा निकाले जाने वाले दो अक्षर क्रम में नहीं होने चाहिए, यह निर्धारित करने के लिए न्यूनतम मान्य लंबाई 3 अक्षर है कि क्या यह एक पैलिंड्रोम है

mom -> true // because it is a palindrome 
moqwm -> qw //because by removing the qw we get mom
mqowm -> ow //because by removing the ow we get mqm ( the o and w are in sequence again but they because q appeared first we kept.
moqm -> q // we only need to remove q

मैं किसी भी मदद की सराहना करूंगा, भले ही वह शुद्ध छद्म कोड हो, मैं बहुत फंस गया हूं। मुझे पता है कि पैलिंड्रोम का उपयोग करके कैसे जांचना है

string.split("").reverse().join("") === string 

लेकिन मुझे यकीन नहीं है कि एक समय में एक चरित्र को कैसे हटाया जाए। और यह भी जांचें कि... स्ट्रिंग का क्रम मायने रखता है, इसलिए मैं विभिन्न विविधताओं को बलपूर्वक लागू नहीं कर सकता।

-1
Frank Dax 14 सितंबर 2020, 15:49

3 जवाब

सबसे बढ़िया उत्तर

आप रिकर्सन का उपयोग कर सकते हैं: दोनों सिरों से वर्णों की तुलना करें जैसे आप पैलिंड्रोम चेक के लिए करेंगे। जब वर्ण भिन्न होते हैं, तो पुनरावर्ती कॉल में दो विकल्पों का प्रयास करें: या तो बाएं वर्ण को हटाए जाने पर विचार करें, या दाएं को।

फ़ंक्शन के लिए एक अतिरिक्त तर्क इंगित कर सकता है कि कितने और हटाने की अनुमति है:

function makePalindrome(str, maxDel = 2) {
    for (let i = 0, j = str.length - 1; i < j; i++, j--) {
        if (str[i] === str[j]) continue;
        if (maxDel === 0) return false;
        // Try by deleting char at j
        let res = makePalindrome(str.slice(i, j), maxDel-1);
        if (res) return (res === true ? "" : res) + str[j]; 
        // Try by deleting char at i 
        res = makePalindrome(str.slice(i+1, j+1), maxDel-1); 
        if (res) return str[i] + (res === true ? "" : res);
        return false;
    }
    return true; // it is a palindrome
}

console.log(makePalindrome("mom"));
console.log(makePalindrome("moqwm"));
console.log(makePalindrome("mqowm"));
console.log(makePalindrome("moqm"));

पुनरावृत्त समाधान

यहां एक पुनरावृत्त समाधान है, विशेष रूप से अधिकतम दो विलोपन के लिए। विचार 4 प्रयास चलाने का है। प्रत्येक प्रयास में हम अलग-अलग निर्णय लेंगे कि जब हमें (पैलिंड्रोमिक) अंतर मिलता है तो किस चरित्र को हटाना है। यहाँ चार प्रयासों का विवरण दिया गया है:

  1. दो हटाने में से प्रत्येक के लिए, दो परस्पर विरोधी वर्णों में से एक को हटा दें
  2. पहले विरोध में, बाएँ वर्ण को हटाएँ; दूसरे संघर्ष के लिए, सही वर्ण हटाएं
  3. पहले विरोध में, सही वर्ण हटाएं; दूसरे विरोध के लिए, बाएँ वर्ण को हटाएँ
  4. दो विलोपनों में से प्रत्येक के लिए, दो परस्पर विरोधी वर्णों में से एक को बाएँ हटाएँ

यहाँ कोड है:

function makePalindrome(str) {
    // Perform 4 attempts which decide what to do when two characters are different:
    //   delete the left one, or delete the right one. So we have 2 options.
    // As there are up to two deletions, we may have 4 options to consider.
    outerLoop: // label for the outer loop
    for (let attempt = 0; attempt < 4; attempt++) {
        let bits = attempt;
        let leftDeleted = "";
        let rightDeleted = "";
        for (let i = 0, j = str.length - 1; i < j; i++, j--) {
            if (str[i] === str[j]) continue;
            if ((leftDeleted + rightDeleted).length >= 2) continue outerLoop; // this attempt failed
            if (bits & 1) { // In this attempt we delete the character at index i
                leftDeleted = leftDeleted + str[i];
                j++; // neutralise the upcoming change to j
            } else { // In this attempt we delete the character at index j
                rightDeleted = str[j] + rightDeleted;
                i--; // neutralise the upcoming change to i
            }
            bits >>= 1; // drop off the used (decision) bit.
        }
        // Success!!
        let res = leftDeleted + rightDeleted;
        return res || true;
    }
    return false;
}

    
console.log(makePalindrome("mom"));
console.log(makePalindrome("moqwm"));
console.log(makePalindrome("mqowm"));
console.log(makePalindrome("moqm"));

अतिरिक्त बाधा जोड़ना

ध्यान दें कि इनमें से कोई भी समाधान जांचता है कि परिणामी पैलिंड्रोम में कम से कम 3 वर्ण हैं या नहीं। यह एक अजीब अतिरिक्त आवश्यकता प्रतीत होती है, लेकिन यदि आप चाहें तो इसे आसानी से जोड़ा जा सकता है।

पहले समाधान में, दूसरा तर्क स्पष्ट रूप से maxDel = Math.min(2, Math.max(0, str.length - 3)) पर सेट होना चाहिए

दूसरे समाधान में, निम्नलिखित if कथन को तदनुसार अनुकूलित करने की आवश्यकता है (2 को उपरोक्त व्यंजक में बदलना):

if ((leftDeleted + rightDeleted).length >= 2)
0
trincot 14 सितंबर 2020, 18:41

समस्या को छोटे चरणों में विभाजित करना आसान है।

तो, आप एक फ़ंक्शन को परिभाषित करके शुरू कर सकते हैं जो किसी दिए गए स्ट्रिंग के विपरीत करेगा:

function reverseString(str) {
   var newString = '';

   for(var i=str.length; i>=0; i--) {
      newString += str.charAt(i);  //this cycle will start from the last char to the first one
   }
  return newString;
}

फिर, सबसे आसान संभव परिणाम क्या है? यह वह मामला है जहां स्ट्रिंग का उल्टा पहले से ही एक पैलिंड्रोम है, इसलिए हम यह कर सकते हैं:

function getPalindrome(str) {
      if (str === reverseString(str)) return true; 
}

फिर, अन्य संभावित परिणामों के लिए, स्ट्रिंग को सबस्ट्रिंग में विभाजित करते हैं और फ़ंक्शन रिवर्स का उपयोग यह जांचने के लिए करते हैं कि स्ट्रिंग एक चार i के बिना एक पैलिंड्रोम है या नहीं। फिर आप इस चार को वापस कर सकते हैं या इसे एक बार में हटा सकते हैं, उदाहरण के लिए:

function getPalinDrome(str) {
    if(str === reverseString(str)) return true; // already a palindrome

    var strlen = str.length;
    for(var i=0; i<strlen; i++) {
        var partialString = str.substring(0, i) + str.substring(i+1, strlen);
        var reversedPartial = reverseString(partialString);
        if(partialString === reversedPartial) {
            return i; //returns the char that needs to be removed to make a palindrome
        }
    }
    return false; //can't do a palindrome
}
    
0
Rute 14 सितंबर 2020, 16:26

यहां एक समाधान है जो पुनरावर्ती खोज का उपयोग करता है जब तक कि स्ट्रिंग की लंबाई 3 (कार्यात्मक शैली में लिखी गई) न हो:

const isPalindrome = (str) =>
  str.split("").reverse().join("") === str ? str : null;

const searchPalindromes = (str) =>
  str.length > 3
    ? str
        .split("")
        .map((_, i) =>
          [isPalindrome, searchPalindromes].map((func) =>
            func(str.slice(0, i) + str.slice(i + 1, str.length))
          )
        )
    : [];

const filterAndFlatten = (arr) => arr.flat(Infinity).filter((x) => x);

const deduplicate = (arr) => [...new Set(arr)];

const compose = (...fns) => (x) => fns.reduceRight((y, f) => f(y), x);

const listPalindromes = compose(
  deduplicate,
  filterAndFlatten,
  searchPalindromes
);

const result = listPalindromes("moqwm");

console.log(result);

यह सबसे कुशल एल्गोरिदम नहीं है क्योंकि यह एक ही स्ट्रिंग को कई बार जांचता है, (इसीलिए deduplicate फ़ंक्शन)। फिर भी यह छोटा और समझने में आसान है।

0
Guerric P 14 सितंबर 2020, 18:09