एकदिश रूप से बढ़ती स्ट्रिंग:
'0' और '1' की एक स्ट्रिंग एकदिश रूप से बढ़ती है यदि इसमें कुछ संख्या में '0' (संभवतः 0) होते हैं, उसके बाद कुछ संख्या में '1' (संभवतः 0 भी) होते हैं।
समस्या
हमें एक JavaScript फ़ंक्शन लिखना है जो एक बाइनरी स्ट्रिंग, str, को पहला और एकमात्र तर्क के रूप में लेता है।
हम स्ट्रिंग में मौजूद किसी भी '0' को '1' में या किसी '1' को '0' में फ्लिप कर सकते हैं। हमारे फ़ंक्शन को S को एकदिश रूप से बढ़ती बनाने के लिए न्यूनतम फ्लिप की संख्या वापस करनी चाहिए।
उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है
इनपुट
const str = '00110';
आउटपुट
const output = 1;
आउटपुट व्याख्या
क्योंकि यदि हम अंतिम '0' को '1' में फ्लिप करते हैं, तो हम '00111' स्ट्रिंग के साथ रह जाएंगे।
उदाहरण
const str = '00110';
const countFlips = (str = '') => {
const map = {};
const helper = (index, prev) => {
map[index] = map[index] || {};
if (map[index][prev] !== undefined) {
return map[index][prev];
}
if (index >= str.length) {
return 0;
}
if (prev === '0') {
if (str[index] === '0') {
map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1);
} else {
map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1);
}
} else if (str[index] === '0') {
map[index][prev] = helper(index + 1, '1') + 1;
} else {
map[index][prev] = helper(index + 1, '1');
}
return map[index][prev];
};
return helper(0, '0');
};
console.log(countFlips(str));
आउटपुट
1
