The red-green-blue color "#AABBCC " can be written as "#ABC " in shorthand.
"#15c " is shorthand for the color "#1155cc ".The similarity between the two colors "#ABCDEF " and "#UVWXYZ " is -(AB - UV)2 - (CD - WX)2 - (EF - YZ)2.
Given a string color that follows the format "#ABCDEF ", return a string represents the color that is most similar to the given color and has a shorthand (i.e., it can be represented as some "#XYZ ").
Any answer which has the same highest similarity as the best answer will be accepted.
Example 1:
Input: color = "#09f166 " Output: "#11ee66 " Explanation: The similarity is -(0x09 - 0x11)2 -(0xf1 - 0xee)2 - (0x66 - 0x66)2 = -64 -9 -0 = -73. This is the highest among any shorthand color.
Example 2:
Input: color = "#4e3fe1 " Output: "#5544dd "
Constraints:
color.length == 7color[0] == '#'color[i] is either digit or character in the range ['a', 'f'] for i > 0.program main
implicit none
integer :: i, j, k
character(len=8) :: color
character(len=4) :: shorthand
real :: similarity
real, parameter :: max_similarity = -1.0e+10
real :: best_similarity = max_similarity
character(len=8), dimension(16) :: colors
data colors / &
"#000000 ", "#111111 ", "#222222 ", "#333333 ", &
"#444444 ", "#555555 ", "#666666 ", "#777777 ", &
"#888888 ", "#999999 ", "#aaaaaa ", "#bbbbbb ", &
"#cccccc ", "#dddddd ", "#eeeeee ", "#ffffff " /
do i = 1, size(colors)
color = colors(i)
do j = 1, size(colors)
if (i /= j) then
shorthand = shorten_color(color)
similarity = similarity_between_colors(color, colors(j))
if (similarity > best_similarity) then
best_similarity = similarity
write (*,*) "Best similarity:", best_similarity, "for color:", color, "shorthand:", shorthand
end if
end if
end do
end do
contains
function shorten_color(color) result(shorthand)
implicit none
character(len=*), intent(in) :: color
character(len=4) :: shorthand
integer :: r, g, b
read (color(2:5), "(H2, H2, H2)") r, g, b
write (shorthand, "(I1, I1, I1)") r, g, b
end function shorten_color
function similarity_between_colors(color1, color2) result(similarity)
implicit none
character(len=*), intent(in) :: color1, color2
integer :: r1, g1, b1, r2, g2, b2
real :: similarity
read (color1(2:5), "(H2, H2, H2)") r1, g1, b1
read (color2(2:5), "(H2, H2, H2)") r2, g2, b2
similarity = -((r1 - r2)**2 - (g1 - g2)**2 - (b1 - b2)**2)
end function similarity_between_colors
end program maintemp.f95:39:28:
39 | read (color(2:5), "(H2, H2, H2)") r, g, b
| 1
Error: Unexpected element ‘,’ in format string at (1)
temp.f95:49:49:
49 | read (color1(2:5), "(H2, H2, H2)") r1, g1, b1
| 1
Warning: Extraneous characters in format at (1)
temp.f95:50:55:
50 | read (color2(2:5), "(H2, H2, H2)") r2, g2, b2
| 1
Warning: Extraneous characters in format at (1)
! Declare variables
integer :: i, j, k, l, m, n
character(len=7) :: color, shorthand
integer :: similarity
! Read input
read(*,*) color
! Initialize variables
similarity = -1
shorthand = "#000000 "
! Loop through all possible shorthand colors
do i = 0, 15
do j = 0, 15
do k = 0, 15
do l = 0, 15
do m = 0, 15
do n = 0, 15
! Calculate similarity
similarity = -((i*16 + j) - (k*16 + l))**2 - ((m*16 + n) - (k*16 + l))**2
! Check if similarity is higher than current best
if (similarity > similarity) then
similarity = similarity
shorthand = "#" // char(i+48) // char(j+48) // char(k+48) // char(l+48) // char(m+48) // char(n+48) // " "
end if
end do
end do
end do
end do
end do
end do
! Output result
write(*,*) shorthand
end
temp.f95:26:132:
26 | shorthand = "#" // char(i+48) // char(j+48) // char(k+48) // char(l+48) // char(m+48) // char(n+48) // " "
| 1
Error: Line truncated at (1) [-Werror=line-truncation]
temp.f95:26:132:
26 | shorthand = "#" // char(i+48) // char(j+48) // char(k+48) // char(l+48) // char(m+48) // char(n+48) // " "
| 1
Error: Unterminated character constant beginning at (1)
f951: some warnings being treated as errors
def letterCasePermutation(s):
def backtrack(index):
if index == len(s):
result.append("".join(s))
return
backtrack(index + 1)
if s[index].isalpha():
s[index] = s[index].swapcase()
backtrack(index + 1)
s[index] = s[index].swapcase()
result = []
s = list(s)
backtrack(0)
return result
The algorithm here is a simple backtracking algorithm. We traverse every character in the input string starting from the first character. For each character, we recursively call the backtrack function considering two cases, one without changing the case, and the other one changing the case, if it is an alphabet.
Before the call, we change the case of the character and change it back after the function call to backtrack to the previous state when exploring other branches of the solution tree.
At the base case, when we reach the end of the input string after considering all characters, we construct the string from the character array and add it to the result list.
The time complexity of this algorithm is O(2^N * N) where N is the length of the string: 2^N is the number of possible solutions, and for each solution, we use O(N) time to construct the string. The space complexity is O(N) due to the function call stack size.
#include <vector>
#include <string>
void backtrack(std::string s, int index, std::vector<std::string>& result) {
if (index == s.length()) {
result.push_back(s);
return;
}
backtrack(s, index + 1, result);
if (isalpha(s[index])) {
s[index] ^= (1 << 5);
backtrack(s, index + 1, result);
}
}
std::vector<std::string> letterCasePermutation(std::string s) {
std::vector<std::string> result;
backtrack(s, 0, result);
return result;
}
The algorithm here is a simple backtracking algorithm. We traverse every character in the input string starting from the first character. For each character, we recursively call the backtrack function considering two cases, one without changing the case, and the other one changing the case, if it is an alphabet.
Before the call, we change the case of the character and change it back after the function call to backtrack to the previous state when exploring other branches of the solution tree.
At the base case, when we reach the end of the input string after considering all characters, we construct the string from the character array and add it to the result list.
The time complexity of this algorithm is O(2^N * N) where N is the length of the string: 2^N is the number of possible solutions, and for each solution, we use O(N) time to construct the string. The space complexity is O(N) due to the function call stack size.