LeetCode Solutions
class Solution {
public:
vector<string> expand(string s) {
vector<string> ans;
string path;
dfs(s, 0, path, ans);
return ans;
}
private:
void dfs(const string& s, int i, string& path, vector<string>& ans) {
if (i == s.length()) {
ans.push_back(path);
return;
}
if (s[i] == '{') {
const int nextRightBraceIndex = s.find_first_of('}', i);
for (const char c :
split(s.substr(i + 1, nextRightBraceIndex - i - 1), ',')) {
path.push_back(c);
dfs(s, nextRightBraceIndex + 1, path, ans);
path.pop_back();
}
} else { // s[i] != '{'
path.push_back(s[i]);
dfs(s, i + 1, path, ans);
path.pop_back();
}
}
vector<char> split(const string& s, char delimiter) {
vector<char> splitted;
for (const char c : s)
if (c != delimiter)
splitted.push_back(c);
return splitted;
}
};
|
class Solution {
public String[] expand(String s) {
List<String> ans = new ArrayList<>();
dfs(s, 0, new StringBuilder(), ans);
Collections.sort(ans);
return ans.toArray(new String[0]);
}
private void dfs(final String s, int i, StringBuilder sb, List<String> ans) {
if (i == s.length()) {
ans.add(sb.toString());
return;
}
if (s.charAt(i) == '{') {
final int nextRightBraceIndex = s.indexOf("}", i);
for (final String c : s.substring(i + 1, nextRightBraceIndex).split(",")) {
sb.append(c);
dfs(s, nextRightBraceIndex + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
} else { // s[i] != '{'
sb.append(s.charAt(i));
dfs(s, i + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
|
class Solution:
def expand(self, s: str) -> List[str]:
ans = []
def dfs(i: int, path: List[str]) -> None:
if i == len(s):
ans.append(''.join(path))
return
if s[i] == '{':
nextRightBraceIndex = s.find('}', i)
for c in s[i + 1:nextRightBraceIndex].split(','):
path.append(c)
dfs(nextRightBraceIndex + 1, path)
path.pop()
else: # s[i] != '{'
path.append(s[i])
dfs(i + 1, path)
path.pop()
dfs(0, [])
return sorted(ans)
|
