Validate Sudoku - Leet Code Solution
Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…
October 06, 2020
You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It’s guaranteed that text contains at least one word.
Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.
Return the string after rearranging the spaces.
Example
Input: text = " this is a sentence "
Output: "this is a sentence"
Input: text = " practice makes perfect"
Output: "practice makes perfect "
Input: text = "hello world"
Output: "hello world"
You need to have three things to solve this problem:
If you have 4 words, and 9 spaces. You will put 9 / (4-1) = 3
spaces in between.
Lets look at the algorithm:
There are some special conditions when
Lets look at the code now
private int process(String text, List<String> words) {
int spaces = 0;
for (int i=0; i<text.length(); ) {
if (text.charAt(i) == ' ') {
while (i < text.length() && text.charAt(i) == ' ') {
spaces ++;
i++;
}
}
else {
StringBuilder sb = new StringBuilder();
while (i < text.length() && text.charAt(i) != ' ') {
sb.append(text.charAt(i));
i++;
}
if (sb.length() > 0) {
words.add(sb.toString());
}
}
}
return spaces;
}
public String reorderSpaces(String text) {
List<String> words = new ArrayList<String>();
int spaces = this.process(text, words);
int divider = (words.size() - 1) > 0 ? (words.size() - 1) : 1;
int targetSpaces = spaces / divider;
int remainingSpaces = spaces % divider;
if (words.size()<= 1) {
remainingSpaces += targetSpaces;
}
StringBuilder sb = new StringBuilder();
if (words.size() > 0) {
sb.append(words.get(0));
}
for (int i=1; i<words.size(); i++) {
for (int j=0; j<targetSpaces; j++) {
sb.append(" ");
}
sb.append(words.get(i));
}
if (remainingSpaces > 0) {
for (int j=0; j<remainingSpaces; j++) {
sb.append(" ");
}
}
return sb.toString();
}
Its O(n)
Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
Problem Statement Say you have an array prices for which the ith element is the…
Introduction You are given an array of integers with size N, and a number K…
Problem Statement Given an array nums of n integers, are there elements a, b, c…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…