Leetcode diary: 1525. 文字列を分割する良い方法の数
1119 ワード
これは新しいシリーズで、リートコードの質問に苦戦している様子を記録しています.たとえ少数の聴衆であっても、継続するモチベーションを与えてくれることを願っています.
この質問は中程度の難易度で DP の質問であるはずだったので、少し気が遠くなりました.そうでもありません笑...
とにかく、私の思考プロセスは次のようなものでした:
1.) 私たちの目標は、左右の一意の文字番号を一致させることです
2.) セットを使用して一意の文字数を保持できます
3.) しかし、それは右辺では機能しません.それぞれの数を数え続ける必要があるため、0 に達したら削除します.
4.) したがって、両方の長所を活かすためにマップを使用します.
5.) 文字列を分割して繰り返すだけです.
以下が実際のコードです.
単なる O(n) であるため、パフォーマンスは非常に優れています.ディスカッションのいくつかの投稿は基本的に同じであるため、これにはトリックがないようです.
これを読んだ後、あなたの心に何か教えてください、ありがとう!
この質問は中程度の難易度で DP の質問であるはずだったので、少し気が遠くなりました.そうでもありません笑...
とにかく、私の思考プロセスは次のようなものでした:
1.) 私たちの目標は、左右の一意の文字番号を一致させることです
2.) セットを使用して一意の文字数を保持できます
3.) しかし、それは右辺では機能しません.それぞれの数を数え続ける必要があるため、0 に達したら削除します.
4.) したがって、両方の長所を活かすためにマップを使用します.
5.) 文字列を分割して繰り返すだけです.
以下が実際のコードです.
var numSplits = function(s) {
const sSplit = s.split('');
const leftSet = new Set();
const rightMap = sSplit.reduce(function(map, letter){
map[letter] = map[letter] ? map[letter]+1 : 1;
return map;
},{});
let goodNum = 0;
sSplit.forEach(function(letter){
leftSet.add(letter);
rightMap[letter]--;
if(rightMap[letter] == 0) { delete rightMap[letter]; }
if(leftSet.size === Object.keys(rightMap).length) {
goodNum++;
}
});
return goodNum;
};
単なる O(n) であるため、パフォーマンスは非常に優れています.ディスカッションのいくつかの投稿は基本的に同じであるため、これにはトリックがないようです.
これを読んだ後、あなたの心に何か教えてください、ありがとう!
Reference
この問題について(Leetcode diary: 1525. 文字列を分割する良い方法の数), 我々は、より多くの情報をここで見つけました https://dev.to/kevin074/leetcode-diary-1525-number-of-good-ways-to-split-a-string-1783テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol